LeetCode 1475. 商品折扣后的最终价格

Categories:

题目描述
思路分析
1. 解法一：单调栈（推荐）
相似题目

题目描述

✅ 1475. 商品折扣后的最终价格

思路分析

解法一：单调栈（推荐）

核心思路：

用单调递增栈保存索引。

当遇到更小或相等价格时，作为前面元素的折扣。

最终价格为 prices[i] - discount[i]。

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(n)。

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] res = new int[n];
        int[] stack = new int[n];
        int top = -1;

        for (int i = 0; i < n; i++) {
            while (top >= 0 && prices[stack[top]] >= prices[i]) {
                int idx = stack[top--];
                res[idx] = prices[idx] - prices[i];
            }
            stack[++top] = i;
        }

        while (top >= 0) {
            int idx = stack[top--];
            res[idx] = prices[idx];
        }
        return res;
    }
}

func finalPrices(prices []int) []int {
    n := len(prices)
    res := make([]int, n)
    stack := make([]int, 0)

    for i := 0; i < n; i++ {
        for len(stack) > 0 && prices[stack[len(stack)-1]] >= prices[i] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[idx] = prices[idx] - prices[i]
        }
        stack = append(stack, i)
    }

    for _, idx := range stack {
        res[idx] = prices[idx]
    }
    return res
}

相似题目

题目	难度	考察点
84. 柱状图中最大的矩形	困难	单调栈
739. 每日温度	中等	单调栈
901. 股票价格跨度	中等	单调栈
1019. 链表中的下一个更大节点	中等	单调栈
503. 下一个更大元素 II	中等	单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/93609742