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 <= 5001 <= prices[i] <= 1000
Solutions
Solution 1: Monotonic Stack
The problem is essentially to find the first element on the right side that is smaller than each element. We can use a monotonic stack to solve this.
We traverse the array prices in reverse order, using the monotonic stack to find the nearest smaller element on the left side of the current element, and then calculate the discount.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array prices.
PythonJavaC++GoTypeScriptRustJavaScriptPHP
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
stk = []
for i in reversed(range(len(prices))):
x = prices[i]
while stk and x < stk[-1]:
stk.pop()
if stk:
prices[i] -= stk[-1]
stk.append(x)
return prices(code-box)
class Solution {
public int[] finalPrices(int[] prices) {
int n = prices.length;
Deque<Integer> stk = new ArrayDeque<>();
for (int i = n - 1; i >= 0; --i) {
int x = prices[i];
while (!stk.isEmpty() && stk.peek() > x) {
stk.pop();
}
if (!stk.isEmpty()) {
prices[i] -= stk.peek();
}
stk.push(x);
}
return prices;
}
}(code-box)
class Solution {
public:
vector<int> finalPrices(vector<int>& prices) {
stack<int> stk;
for (int i = prices.size() - 1; ~i; --i) {
int x = prices[i];
while (!stk.empty() && stk.top() > x) {
stk.pop();
}
if (!stk.empty()) {
prices[i] -= stk.top();
}
stk.push(x);
}
return prices;
}
};(code-box)
func finalPrices(prices []int) []int {
stk := []int{}
for i := len(prices) - 1; i >= 0; i-- {
x := prices[i]
for len(stk) > 0 && stk[len(stk)-1] > x {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
prices[i] -= stk[len(stk)-1]
}
stk = append(stk, x)
}
return prices
}(code-box)
function finalPrices(prices: number[]): number[] {
const stk: number[] = [];
for (let i = prices.length - 1; ~i; --i) {
const x = prices[i];
while (stk.length && stk.at(-1)! > x) {
stk.pop();
}
prices[i] -= stk.at(-1) || 0;
stk.push(x);
}
return prices;
}(code-box)
impl Solution {
pub fn final_prices(mut prices: Vec<i32>) -> Vec<i32> {
let mut stk: Vec<i32> = Vec::new();
for i in (0..prices.len()).rev() {
let x = prices[i];
while !stk.is_empty() && x < *stk.last().unwrap() {
stk.pop();
}
if let Some(&top) = stk.last() {
prices[i] -= top;
}
stk.push(x);
}
prices
}
}(code-box)
/**
* @param {number[]} prices
* @return {number[]}
*/
var finalPrices = function (prices) {
const stk = [];
for (let i = prices.length - 1; ~i; --i) {
const x = prices[i];
while (stk.length && stk.at(-1) > x) {
stk.pop();
}
prices[i] -= stk.at(-1) || 0;
stk.push(x);
}
return prices;
};(code-box)
class Solution {
/**
* @param Integer[] $prices
* @return Integer[]
*/
function finalPrices($prices) {
$stk = [];
$n = count($prices);
for ($i = $n - 1; $i >= 0; $i--) {
$x = $prices[$i];
while (!empty($stk) && $x < end($stk)) {
array_pop($stk);
}
if (!empty($stk)) {
$prices[$i] -= end($stk);
}
$stk[] = $x;
}
return $prices;
}
}(code-box)
