给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。

商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。

请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。

示例 1：

输入：prices = [8,4,6,2,3]
输出：[4,2,4,2,3]
解释：
商品 0 的价格为 price[0]=8 ，你将得到 prices[1]=4 的折扣，所以最终价格为 8 - 4 = 4 。
商品 1 的价格为 price[1]=4 ，你将得到 prices[3]=2 的折扣，所以最终价格为 4 - 2 = 2 。
商品 2 的价格为 price[2]=6 ，你将得到 prices[3]=2 的折扣，所以最终价格为 6 - 2 = 4 。
商品 3 和 4 都没有折扣。
示例 2：

输入：prices = [1,2,3,4,5]
输出：[1,2,3,4,5]
解释：在这个例子中，所有商品都没有折扣。
示例 3：

输入：prices = [10,1,1,6]
输出：[9,0,1,6]

提示：

1 <= prices.length <= 500
1 <= prices[i] <= 10^3

  1. class Solution {
  2.     public int[] finalPrices(int[] prices) {
  3.         int n = prices.length;
  4.         int[] res = new int[n];
  5.         for (int i = 0; i < n; ++i) {
  6.             int j = i + 1;
  7.             while (j < n && prices[j] > prices[i]) j++;
  8.             res[i] = prices[i];
  9.             if (j < n) res[i] -= prices[j];
  10.         }
  11.         return res;
  12.     }
  13. }

单调栈

  1. class Solution {
  2.     //单调上升栈,找后面第一个小于等于的数
  3.     int[] st;
  4.     int tt;
  5.     public int[] finalPrices(int[] prices) {
  6.         int n = prices.length;
  7.         int[] newPrices = new int[n + 1];
  8.         System.arraycopy(prices, 0, newPrices, 0, n);
  9.         newPrices[n] = -1;
  10.         int[] res = new int[n];
  11.         n++;
  12.         prices = newPrices;
  13.         st = new int[n + 10];
  14.         for (int i = 0; i < n; ++i) {
  15.             while (tt > 0 && prices[st[tt]] >= prices[i]) {
  16.                 int cur = st[tt--];
  17.                 res[cur] = prices[cur];
  18.                 if (prices[i] != -1) //判断是不是哨兵
  19.                     res[cur] -= prices[i];
  20.             }
  21.             st[++tt] = i;
  22.         }
  23.         return res;
  24.     }
  25. }