顺序遍历，用 Label 或 continue 2 继续外层循环，单调栈（顺序遍历 / 倒序遍历），3 解法求解《1475. 商品折扣后的最终价格》

代码数据结构:栈数据结构:单调栈遍历:顺序遍历遍历:倒序遍历语言:JavaScript语言:Go语言:PHP语言:Python语言:C语言:C++语言:C#语言:TypeScript语言:Java
2022-09-01 06:37:08
顺序遍历，用 Label 或 continue 2 继续外层循环，单调栈（顺序遍历 / 倒序遍历），3 解法求解《1475. 商品折扣后的最终价格》

例题

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

给你一个数组 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

答案

顺序遍历 · 跳出循环

使用 Label 或 continue 2 跳出当前循环，继续外层循环 

var finalPrices = function(prices) {
  const n = prices.length
  label: for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (prices[j] <= prices[i]) {
        prices[i] -= prices[j]
        continue label
      }
    }
  }
  return prices
};
function finalPrices(prices: number[]): number[] {
  let n = prices.length
  label: for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (prices[j] <= prices[i]) {
        prices[i] -= prices[j]
        continue label
      }
    }
  }
  return prices
};
class Solution {
  function finalPrices($prices) {
    $n = count($prices);
    foreach ($prices as $i => $v) {
      for ($j = $i + 1; $j < $n; $j++) {
        if ($prices[$j] <= $prices[$i]) {
          $prices[$i] -= $prices[$j];
          continue 2;
        }
      }
    }
    return $prices;
  }
}
func finalPrices(prices []int) []int {
  n := len(prices)
  label: for i, price := range prices {
    for j := i + 1; j < n; j++ {
      if prices[j] <= price {
        prices[i] -= prices[j]
        continue label
      }
    }
  }
  return prices
}
class Solution {
  public int[] finalPrices(int[] prices) {
    int n = prices.length;
    label: for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if (prices[j] <= prices[i]) {
          prices[i] -= prices[j];
          continue label;
        }
      }
    }
    return prices;
  }
}
public class Solution { // goto
  public int[] FinalPrices(int[] prices) {
    int n = prices.Length;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if (prices[j] <= prices[i]) {
          prices[i] -= prices[j];
          goto label;
        }
      }
      label:;
    }
    return prices;
  }
}
public class Solution { // break
  public int[] FinalPrices(int[] prices) {
    int n = prices.Length;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if (prices[j] <= prices[i]) {
          prices[i] -= prices[j];
          break;
        }
      }
    }
    return prices;
  }
}
int* finalPrices(int* prices, int pricesSize, int* returnSize){ // goto
  for (int i = 0; i < pricesSize; i++) {
    for (int j = i + 1; j < pricesSize; j++) {
      if (prices[j] <= prices[i]) {
        prices[i] -= prices[j];
        goto label;
      }
    }
    label:;
  }
  *returnSize = pricesSize;
  return prices;
}
int* finalPrices(int* prices, int pricesSize, int* returnSize){ // break
  for (int i = 0; i < pricesSize; i++) {
    for (int j = i + 1; j < pricesSize; j++) {
      if (prices[j] <= prices[i]) {
        prices[i] -= prices[j];
        break;
      }
    }
  }
  *returnSize = pricesSize;
  return prices;
}
class Solution {
public:
  vector<int> finalPrices(vector<int>& prices) { // goto
    int n = prices.size();
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if (prices[j] <= prices[i]) {
          prices[i] -= prices[j];
          goto label;
        }
      }
      label:;
    }
    return prices;
  }
};
class Solution {
public:
  vector<int> finalPrices(vector<int>& prices) { // break
    int n = prices.size();
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if (prices[j] <= prices[i]) {
          prices[i] -= prices[j];
          break;
        }
      }
    }
    return prices;
  }
};
class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    for i, price in enumerate(prices):
      for j in range(i + 1, len(prices)):
        if prices[j] <= prices[i]: 
          prices[i] -= prices[j]
          break
    return prices

倒序遍历 · 单调栈 · 存价格
  1. 倒序遍历：> 当前价格的历史价格，弹出栈（栈中，都是 <= 当前价格）
  2. 放入当前价格

var finalPrices = function(prices) {
  const stack = []
  for (let i = prices.length; i--;) {
    const t = prices[i]
    while (stack.length && stack[stack.length - 1] > t) stack.pop()
    if (stack.length) prices[i] -= stack[stack.length - 1]
    stack.push(t)
  }
  return prices
};
function finalPrices(prices: number[]): number[] {
  const stack = []
  for (let i = prices.length; i--;) {
    const t = prices[i]
    while (stack.length && stack[stack.length - 1] > t) stack.pop()
    if (stack.length) prices[i] -= stack[stack.length - 1]
    stack.push(t)
  }
  return prices
};
class Solution {
  function finalPrices($prices) {
    $stack = [];
    for ($i = count($prices); $i--;) {
      $t = $prices[$i];
      while (count($stack) && end($stack) > $prices[$i]) array_pop($stack);
      if (count($stack)) $prices[$i] -= end($stack);
      $stack []= $t;
    }
    return $prices;
  }
}
func finalPrices(prices []int) []int {
  stack := []int{}
  for i := len(prices) - 1; i >= 0; i-- {
    t := prices[i]
    for len(stack) > 0 && stack[len(stack) - 1] > t {
      stack = stack[:len(stack) - 1]
    }
    if len(stack) > 0 {
      prices[i] -= stack[len(stack) - 1]
    }
    stack = append(stack, t)
  }
  return prices
}
class Solution {
  public int[] finalPrices(int[] prices) {
    Deque<Integer> stack = new ArrayDeque<Integer>();
    for (int i = prices.length - 1; i >= 0; i--) {
      int t = prices[i];
      while (stack.isEmpty() == false && stack.peek() > t) stack.pop();
      if (stack.isEmpty() == false) prices[i] -= stack.peek();
      stack.push(t);
    }
    return prices;
  }
}
public class Solution {
  public int[] FinalPrices(int[] prices) {
    Stack<int> stack = new Stack<int>();
    for (int i = prices.Length - 1; i >= 0; i--) {
      int t = prices[i];
      while (stack.Count > 0 && stack.Peek() > t) stack.Pop();
      if (stack.Count > 0) prices[i] -= stack.Peek();
      stack.Push(t);
    }
    return prices;
  }
}
int* finalPrices(int* prices, int pricesSize, int* returnSize){ // break
  int* stack = malloc(sizeof(int) * pricesSize);
  for (int i = pricesSize, j = 0; i--;) {
    int t = prices[i];
    while (j && stack[j - 1] > t) j--;
    if (j) prices[i] -= stack[j - 1];
    stack[j++] = t;
  }
  free(stack);
  *returnSize = pricesSize;
  return prices;
}
class Solution {
public:
  vector<int> finalPrices(vector<int>& prices) {
    stack<int> st;
    for (int i = prices.size(); i--;) {
      int t = prices[i];
      while (st.empty() == false && st.top() > t) st.pop();
      if (st.empty() == false) prices[i] -= st.top();
      st.emplace(t);
    }
    return prices;
  }
};
class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    stack = []
    for i in range(len(prices) - 1, -1, -1):
      t = prices[i]
      while len(stack) and stack[-1] > t: stack.pop()
      if len(stack): prices[i] -= stack[-1]
      stack.append(t)
    return prices

顺序遍历 · 单调栈 · 存下标
  1. 顺序遍历：找 当前价格 <= 栈顶价格
  2. 更新栈中下标，对应位置的价格

var finalPrices = function(prices) {
  const stack = [], n = prices.length
  for (let i = 0; i < n; i++) {
    while (stack.length && prices[stack[stack.length - 1]] >= prices[i]) {
      prices[stack.pop()] -= prices[i]
    }
    stack.push(i)
  }
  return prices
};
function finalPrices(prices: number[]): number[] {
  const stack = [], n = prices.length
  for (let i = 0; i < n; i++) {
    while (stack.length && prices[stack[stack.length - 1]] >= prices[i]) {
      prices[stack.pop()] -= prices[i]
    }
    stack.push(i)
  }
  return prices
};
class Solution {
  function finalPrices($prices) {
    $stack = [];
    foreach ($prices as $i => $price) {
      while (count($stack) && $prices[end($stack)] >= $price) $prices[array_pop($stack)] -= $price;
      $stack []= $i;
    }
    return $prices;
  }
}
func finalPrices(prices []int) []int {
  stack := []int{}
  for i, price := range prices {
    for len(stack) > 0 && prices[stack[len(stack) - 1]] >= price {
      prices[stack[len(stack) - 1]] -= price
      stack = stack[:len(stack) - 1]
    }
    stack = append(stack, i)
  }
  return prices
}
class Solution {
  public int[] finalPrices(int[] prices) {
    Deque<Integer> stack = new ArrayDeque<Integer>();
    int n = prices.length;
    for (int i = 0; i < n; i++) {
      while (stack.isEmpty() == false && prices[stack.peek()] >= prices[i]) {
        prices[stack.pop()] -= prices[i];
      }
      stack.push(i);
    }
    return prices;
  }
}
public class Solution {
  public int[] FinalPrices(int[] prices) {
    Stack<int> stack = new Stack<int>();
    int n = prices.Length;
    for (int i = 0; i < n; i++) {
      while (stack.Count > 0 && prices[stack.Peek()] >= prices[i]) {
        prices[stack.Pop()] -= prices[i];
      }
      stack.Push(i);
    }
    return prices;
  }
}
int* finalPrices(int* prices, int pricesSize, int* returnSize){
  int* stack = malloc(sizeof(int) * pricesSize);
  for (int i = 0, j = 0; i < pricesSize; i++) {
    while (j > 0 && prices[stack[j - 1]] >= prices[i]) prices[stack[j-- - 1]] -= prices[i];
    stack[j++] = i; 
  }
  free(stack);
  *returnSize = pricesSize;
  return prices;
}
class Solution {
public:
  vector<int> finalPrices(vector<int>& prices) {
    stack<int> st;
    int n = prices.size();
    for (int i = 0; i < n; i++) {
      while (st.empty() == false && prices[st.top()] >= prices[i]) {
        prices[st.top()] -= prices[i];
        st.pop();
      }
      st.push(i);
    }
    return prices;
  }
};
class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    stack = list()
    for i, price in enumerate(prices):
      while len(stack) and prices[stack[-1]] >= price: prices[stack.pop()] -= price
      stack.append(i)
    return prices

Shon
Github　力扣　M站　全部原创，请勿转载
暴力，贪心算法，三次遍历（倒序 + 正序 + 倒序），一次遍历（倒序），数字转列表，列表转数字，交换变量（临时变量 / 指针交换 / 加减法 / 解构赋值 / 位运算 / 求和减赋值法），3 解法求解《670. 最大交换》
暴力，贪心算法，三次遍历（倒序 + 正序 + 倒序），一次遍历（倒序），数字转列表（Array.from / str_split / []byte(strconv.Itoa()) / String.valueOf().toCharArray() / ToString().ToCharArray() / sprintf(s, "%d", num) / to_string / list(str())），列……
顺序遍历 + 二分查找算法，升序 或 降序 排序，5 解法求解《1608. 特殊数组的特征值》
顺序遍历 + 二分查找算法，升序 或 降序 排序，lower_bound / bisect_left / sort.Search 枚举 x，5 解法求解《1608. 特殊数组的特征值》
顺序遍历，栈，用 reduce / array_reduce / stream().reduce / Aggregate / accumulate 累积完成 1 行解，3 解法求解《1598. 文件夹操作日志搜集器》，
顺序遍历，栈，2 解法求解《1598. 文件夹操作日志搜集器》，用 reduce / array_reduce / stream().reduce / Aggregate / accumulate 累积完成 1 行解