切換語言為:簡體

商品折扣後的最終價格單調棧

  • 爱糖宝
  • 2024-11-23
  • 2027
  • 0
  • 0

給你一個數組 prices ,其中 prices[i] 是商店裏第 i 件商品的價格。 商店裏正在進行促銷活動,如果你要買第 i 件商品,那麼你可以得到與 prices[j] 相等的折扣,其中 j 是滿足 j > i 且 prices[j] <= prices[i] 的 最小下標 ,如果沒有滿足條件的 j ,你將沒有任何折扣。 請你返回一個數組,陣列中第 i 個元素是折扣後你購買商品 i 最終需要支付的價格。

輸入: prices = [8,4,6,2,3]
輸出: [4,2,4,2,3]

class Solution {
    public int[] finalPrices(int[] prices) {
        int n=prices.length;
        int[] ans=new int[n];
        Deque<Integer> stack=new ArrayDeque<Integer>();
        for(int i=n-1;i>=0;i--){
            while(!stack.isEmpty() && stack.peek()>prices[i]){
                stack.pop();
            }
            ans[i]=stack.isEmpty()?prices[i]:prices[i]-stack.peek();
            stack.push(prices[i]);
        }
        return ans;
    }
}


0則評論

您的電子郵件等資訊不會被公開,以下所有項目均必填

OK! You can skip this field.