Question

1475. Final Prices With a Special Discount in a Shop

中文文档

Description

You are given an integer array prices where prices[i] is the price of the ith item in a shop.

There is a special discount for items in the shop. If you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all.

Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop, considering the special discount.

 

Example 1:

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation: 
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4.
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2.
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4.
For items 3 and 4 you will not receive any discount at all.

Example 2:

Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: In this case, for all items, you will not receive any discount at all.

Example 3:

Input: prices = [10,1,1,6]
Output: [9,0,1,6]

 

Constraints:

• 1 <= prices.length <= 500
• 1 <= prices[i] <= 1000

Solutions

Solution 1

class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    ans = []
    for i, v in enumerate(prices):
      ans.append(v)
      for j in range(i + 1, len(prices)):
        if prices[j] <= v:
          ans[-1] -= prices[j]
          break
    return ans

class Solution {
  public int[] finalPrices(int[] prices) {
    int n = prices.length;
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      ans[i] = prices[i];
      for (int j = i + 1; j < n; ++j) {
        if (prices[j] <= prices[i]) {
          ans[i] -= prices[j];
          break;
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> finalPrices(vector<int>& prices) {
    int n = prices.size();
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
      ans[i] = prices[i];
      for (int j = i + 1; j < n; ++j) {
        if (prices[j] <= prices[i]) {
          ans[i] -= prices[j];
          break;
        }
      }
    }
    return ans;
  }
};

func finalPrices(prices []int) []int {
  n := len(prices)
  ans := make([]int, n)
  for i, v := range prices {
    ans[i] = v
    for j := i + 1; j < n; j++ {
      if prices[j] <= v {
        ans[i] -= prices[j]
        break
      }
    }
  }
  return ans
}

function finalPrices(prices: number[]): number[] {
  const n = prices.length;
  const ans = new Array(n);
  for (let i = 0; i < n; ++i) {
    ans[i] = prices[i];
    for (let j = i + 1; j < n; ++j) {
      if (prices[j] <= prices[i]) {
        ans[i] -= prices[j];
        break;
      }
    }
  }
  return ans;
}

impl Solution {
  pub fn final_prices(prices: Vec<i32>) -> Vec<i32> {
    let n = prices.len();
    let mut stack = Vec::new();
    let mut res = vec![0; n];
    for i in (0..n).rev() {
      let price = prices[i];
      while !stack.is_empty() && *stack.last().unwrap() > price {
        stack.pop();
      }
      res[i] = price - stack.last().unwrap_or(&0);
      stack.push(price);
    }
    res
  }
}

/**
 * @param {number[]} prices
 * @return {number[]}
 */
var finalPrices = function (prices) {
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      if (prices[i] >= prices[j]) {
        prices[i] -= prices[j];
        break;
      }
    }
  }
  return prices;
};

class Solution {
  /**
   * @param Integer[] $prices
   * @return Integer[]
   */
  function finalPrices($prices) {
    for ($i = 0; $i < count($prices); $i++) {
      for ($j = $i + 1; $j < count($prices); $j++) {
        if ($prices[$i] >= $prices[$j]) {
          $prices[$i] -= $prices[$j];
          break;
        }
      }
    }
    return $prices;
  }
}

Solution 2

class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    stk = []
    ans = prices[:]
    for i, v in enumerate(prices):
      while stk and prices[stk[-1]] >= v:
        ans[stk.pop()] -= v
      stk.append(i)
    return ans

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

class Solution {
public:
  vector<int> finalPrices(vector<int>& prices) {
    stack<int> stk;
    vector<int> ans = prices;
    for (int i = 0; i < prices.size(); ++i) {
      while (!stk.empty() && prices[stk.top()] >= prices[i]) {
        ans[stk.top()] -= prices[i];
        stk.pop();
      }
      stk.push(i);
    }
    return ans;
  }
};

func finalPrices(prices []int) []int {
  var stk []int
  n := len(prices)
  ans := make([]int, n)
  for i, v := range prices {
    ans[i] = v
    for len(stk) > 0 && prices[stk[len(stk)-1]] >= v {
      ans[stk[len(stk)-1]] -= v
      stk = stk[:len(stk)-1]
    }
    stk = append(stk, i)
  }
  return ans
}

function finalPrices(prices: number[]): number[] {
  const n = prices.length;
  const stk = [];
  const ans = new Array(n);
  for (let i = 0; i < n; ++i) {
    ans[i] = prices[i];
    while (stk.length && prices[stk[stk.length - 1]] >= prices[i]) {
      ans[stk.pop()] -= prices[i];
    }
    stk.push(i);
  }
  return ans;
}

Solution 3

class Solution:
  def finalPrices(self, prices: List[int]) -> List[int]:
    stk = []
    ans = prices[:]
    for i in range(len(prices) - 1, -1, -1):
      while stk and prices[stk[-1]] > prices[i]:
        stk.pop()
      if stk:
        ans[i] -= prices[stk[-1]]
      stk.append(i)
    return ans

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

class Solution {
public:
  vector<int> finalPrices(vector<int>& prices) {
    stack<int> stk;
    int n = prices.size();
    vector<int> ans(n);
    for (int i = n - 1; i >= 0; --i) {
      ans[i] = prices[i];
      while (!stk.empty() && prices[stk.top()] > prices[i]) {
        stk.pop();
      }
      if (!stk.empty()) {
        ans[i] -= prices[stk.top()];
      }
      stk.push(i);
    }
    return ans;
  }
};

func finalPrices(prices []int) []int {
  stk := []int{}
  n := len(prices)
  ans := make([]int, n)
  for i := n - 1; i >= 0; i-- {
    ans[i] = prices[i]
    for len(stk) > 0 && prices[stk[len(stk)-1]] > prices[i] {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      ans[i] -= prices[stk[len(stk)-1]]
    }
    stk = append(stk, i)
  }
  return ans
}

function finalPrices(prices: number[]): number[] {
  const n = prices.length;
  const stack = [];
  const res = new Array(n);
  for (let i = n - 1; i >= 0; i--) {
    const price = prices[i];
    while (stack.length !== 0 && stack[stack.length - 1] > price) {
      stack.pop();
    }
    res[i] = price - (stack[stack.length - 1] ?? 0);
    stack.push(price);
  }
  return res;
}