monotonic stack Archives - Huahua's Tech Road

花花酱 LeetCode 1776. Car Fleet II

By zxi on February 27, 2021

There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array cars of length n, where cars[i] = [position_i, speed_i] represents:

position_i is the distance between the i^th car and the beginning of the road in meters. It is guaranteed that position_i < position_i+1.
speed_i is the initial speed of the i^th car in meters per second.

For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the slowest car in the fleet.

Return an array answer, where answer[i] is the time, in seconds, at which the i^th car collides with the next car, or -1 if the car does not collide with the next car. Answers within 10^-5 of the actual answers are accepted.

Example 1:

Input: cars = [[1,2],[2,1],[4,3],[7,2]]
Output: [1.00000,-1.00000,3.00000,-1.00000]
Explanation: After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.

Example 2:

Input: cars = [[3,4],[5,4],[6,3],[9,1]]
Output: [2.00000,1.00000,1.50000,-1.00000]

Constraints:

1 <= cars.length <= 10⁵
1 <= position_i, speed_i <= 10⁶
position_i < position_i+1

Solution: Monotonic Stack

Key observation: If my speed is slower than the speed of the previous car, not only mine but also all cars behind me will NEVER be able to catch/collide with the previous car. Such that we can throw it away.

Maintain a stack that stores the indices of cars with increasing speed.

Process car from right to left, for each car, pop the stack (throw the fastest car away) if any of the following conditions hold.
1) speed <= stack.top().speed
2) There are more than one car before me and it takes more than to collide the fastest car than time the fastest took to collide.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<double> getCollisionTimes(vector<vector<int>>& cars) {

auto collide = [&](int i, int j) -> double {

return static_cast<double>(cars[i][0] - cars[j][0]) /

(cars[j][1] - cars[i][1]);

};

const int n = cars.size();

vector<double> ans(n, -1);

stack<int> s;

for (int i = n - 1; i >= 0; --i) {

while (!s.empty() && (cars[i][1] <= cars[s.top()][1] ||

(s.size() > 1 && collide(i, s.top()) > ans[s.top()])))

s.pop();

ans[i] = s.empty() ? -1 : collide(i, s.top());

s.push(i);

}

return ans;

}

};

花花酱 LeetCode 1475. Final Prices With a Special Discount in a Shop

By zxi on June 13, 2020

Given the 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 array where the ith element 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] <= 10^3

Solution 1: Simulation

Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> finalPrices(vector<int> prices) {

const 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;

}

};

Solution 2: Monotonic Stack

Use a stack to store monotonically increasing items, when the current item is cheaper than the top of the stack, we get the discount and pop that item. Repeat until the current item is no longer cheaper or the stack becomes empty.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> finalPrices(vector<int> prices) {

// stores pointers of monotonically incraseing elements.

stack<int*> s;

for (int& p : prices) {

while (!s.empty() && *s.top() >= p) {

*s.top() -= p;

s.pop();

}

s.push(&p);

}

return prices;

}

};

index version

C++

// Author: Huahua

class Solution {

public:

vector<int> finalPrices(vector<int> prices) {

// stores indices of monotonically incraseing elements.

stack<int> s;

for (int i = 0; i < prices.size(); ++i) {

while (!s.empty() && prices[s.top()] >= prices[i]) {

prices[s.top()] -= prices[i];

s.pop();

}

s.push(i);

}

return prices;

}

};

花花酱 LeetCode 84. Largest Rectangle in Histogram

By zxi on February 14, 2020

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Solution 1: Monotonic Stack

Use a monotonic stack to maintain the higher bars’s indices in ascending order.
When encounter a lower bar, pop the tallest bar and use it as the bottleneck to compute the area.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 12ms, 10.7MB

class Solution {

public:

int largestRectangleArea(vector<int>& heights) {

heights.push_back(0);

const int n = heights.size();

stack<int> s;

int ans = 0;

int i = 0;

while (i < n) {

if (s.empty() || heights[i] >= heights[s.top()]) {

s.push(i++);

} else {

int h = heights[s.top()]; s.pop();

int w = s.empty() ? i : i - s.top() - 1;

ans = max(ans, h * w);

}

return ans;

}

};

Posts tagged as “monotonic stack”

花花酱 LeetCode 1776. Car Fleet II

Solution: Monotonic Stack

C++

花花酱 LeetCode 1475. Final Prices With a Special Discount in a Shop

Solution 1: Simulation

C++

Solution 2: Monotonic Stack

C++

C++

花花酱 LeetCode 84. Largest Rectangle in Histogram

Solution 1: Monotonic Stack

C++