Skip to content

Commit a85d732

Browse files
gazeldxgazeldx
committed
0084-largest-rectangle-in-histogram.md Added 7 languages' solutions.
1 parent 5188ac2 commit a85d732

File tree

2 files changed

+264
-0
lines changed

2 files changed

+264
-0
lines changed

‎README.md

+1
Original file line numberDiff line numberDiff line change
@@ -67,5 +67,6 @@ After finishing one category of questions, you can study another category to imp
6767
- [739. Daily Temperatures](problems/0739-daily-temperatures.md)
6868
- [496. Next Greater Element I](problems/0496-next-greater-element-i.md)
6969
- [42. Trapping Rain Water](problems/0042-trapping-rain-water.md)
70+
- [84. Largest Rectangle in Histogram](0084-largest-rectangle-in-histogram.md)
7071

7172
More LeetCode problems will be added soon...

‎problems/0084-largest-rectangle-in-histogram.md

+263
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,263 @@
1+
# 84. Largest Rectangle in Histogram
2+
LeetCode problem: [84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)
3+
4+
## LeetCode problem description
5+
Given an array of integers `heights` representing the histogram's bar height where the width of each bar is `1`, return the area of the largest rectangle in the histogram.
6+
7+
```
8+
------------------------------------------------------------------------
9+
[Example 1]
10+
11+
Input: heights = [2,1,5,6,2,3]
12+
Output: 10
13+
14+
Explanation: The above is a histogram where width of each bar is 1.
15+
The largest rectangle is shown in the red area, which has an area = 10 units.
16+
------------------------------------------------------------------------
17+
[Example 2]
18+
19+
Input: heights = [2,4]
20+
Output: 4
21+
------------------------------------------------------------------------
22+
[Constraints]
23+
24+
1 <= heights.length <= 100000
25+
0 <= heights[i] <= 10000
26+
------------------------------------------------------------------------
27+
```
28+
29+
## Thoughts
30+
This problem can be solved using **Monotonic Stack**.
31+
32+
* The `heights` in the stack from bottom to top are in ascending order.
33+
* While `current_height < stack_top_height`, pop `stack_top_height`.
34+
* Follow **Monotonic Stack**'s common rule: **only calculating when `pop()` is happening**. This common rule can be applied to calculating result for **most** of the `Monotonic Stack` problems.
35+
* Disappeared heights (popped by `current_height` or popped by `stack_top_height`) are all taller than `stack_top_height`. This logic will be used to calculate the `width`.
36+
37+
Detailed solutions will be given later, and now only the best practices in 7 languages are given.
38+
39+
### Complexity
40+
* Time: `O(n)`.
41+
* Space: `O(n)`.
42+
43+
## Python
44+
```python
45+
class Solution:
46+
def largestRectangleArea(self, heights: List[int]) -> int:
47+
heights = [0] + heights + [0]
48+
max_area = 0
49+
index_stack = []
50+
51+
for i, height in enumerate(heights):
52+
while index_stack and height < heights[index_stack[-1]]:
53+
popped_index = index_stack.pop()
54+
55+
popped_height = heights[popped_index]
56+
57+
left_index = index_stack[-1] # popped_height's remaining left heights are all shorter than 'popped_height', because when 'popped_height' itself was pushed into stack, it must have caused some (could be none) taller heights been popped out of the stack.
58+
right_index = i # popped_height's right heights (which are all taller than 'popped_height') have been popped out of the stack (disappeared) when current `i` height is being pushed into stack.
59+
width = right_index - left_index - 1 # So in the range of 'width', they are all no shorter than `popped_height`, although they have been popped out of the stack (disappeared).
60+
61+
area = popped_height * width
62+
if area > max_area:
63+
max_area = area
64+
65+
index_stack.append(i)
66+
67+
return max_area
68+
```
69+
70+
## Java
71+
```java
72+
class Solution {
73+
public int largestRectangleArea(int[] heightArray) {
74+
var heights = new int[heightArray.length + 2];
75+
System.arraycopy(heightArray, 0, heights, 1, heightArray.length);
76+
77+
var maxArea = 0;
78+
var indexStack = new Stack<Integer>();
79+
80+
for (var i = 0; i < heights.length; i++) {
81+
while (!indexStack.empty() && heights[i] < heights[indexStack.peek()]) {
82+
var poppedIndex = indexStack.pop();
83+
84+
var poppedHeight = heights[poppedIndex];
85+
var leftIndex = indexStack.peek(); // poppedHeight's remaining left heights are all shorter than it, because when 'poppedHeight' itself was pushed into stack, it must have caused some (could be none) taller heights been popped out of the stack.
86+
var rightIndex = i; // poppedHeight's right heights (which are all taller than 'poppedHeight') have been popped out of the stack (disappeared) when current `i` height is being pushed into stack.
87+
var width = rightIndex - leftIndex - 1; // So in the range of 'width', they are all no shorter than `poppedHeight`, although they have been popped out of the stack (disappeared).
88+
89+
var area = poppedHeight * width;
90+
if (area > maxArea) {
91+
maxArea = area;
92+
}
93+
}
94+
95+
indexStack.push(i);
96+
}
97+
98+
return maxArea;
99+
}
100+
}
101+
```
102+
103+
## C++
104+
```cpp
105+
class Solution {
106+
public:
107+
int largestRectangleArea(vector<int> heights) {
108+
heights.insert(heights.begin(), 0);
109+
heights.emplace_back(0);
110+
auto max_area = 0;
111+
stack<int> index_stack;
112+
113+
for (auto i = 0; i < heights.size(); i++) {
114+
while (!index_stack.empty() && heights[i] < heights[index_stack.top()]) {
115+
auto popped_height = heights[index_stack.top()];
116+
117+
index_stack.pop();
118+
119+
auto left_index = index_stack.top(); // popped_height's remaining left heights are all shorter than it, because when 'popped_height' itself was pushed into stack, it must have caused some (could be none) taller heights been popped out of the stack.
120+
auto right_index = i; // popped_height's right heights (which are all taller than 'popped_height') have been popped out of the stack (disappeared) when current `i` height is being pushed into stack.
121+
auto width = right_index - left_index - 1; // So in the range of 'width', they are all no shorter than `popped_height`, although they have been popped out of the stack (disappeared).
122+
123+
auto area = popped_height * width;
124+
if (area > max_area) {
125+
max_area = area;
126+
}
127+
}
128+
129+
index_stack.push(i);
130+
}
131+
132+
return max_area;
133+
}
134+
};
135+
```
136+
137+
## JavaScript
138+
```javascript
139+
var largestRectangleArea = function(heights) {
140+
let maxArea = 0
141+
const indexStack = []
142+
heights = [0, ...heights, 0]
143+
144+
heights.forEach((height, i) => {
145+
while (indexStack.length > 0 && height < heights[indexStack.at(-1)]) {
146+
const poppedIndex = indexStack.pop()
147+
148+
const poppedHeight = heights[poppedIndex]
149+
const leftIndex = indexStack.at(-1) // poppedHeight's remaining left heights are all shorter than it, because when 'poppedHeight' itself was pushed into stack, it must have caused some (could be none) taller heights been popped out of the stack.
150+
const rightIndex = i // poppedHeight's right heights (which are all taller than 'poppedHeight') have been popped out of the stack (disappeared) when current `i` height is being pushed into stack.
151+
const width = rightIndex - leftIndex - 1 // So in the range of 'width', they are all no shorter than `poppedHeight`, although they have been popped out of the stack (disappeared).
152+
153+
const area = poppedHeight * width
154+
if (area > maxArea) {
155+
maxArea = area
156+
}
157+
}
158+
159+
indexStack.push(i)
160+
})
161+
162+
return maxArea
163+
};
164+
```
165+
166+
## C#
167+
```c#
168+
public class Solution {
169+
public int LargestRectangleArea(int[] heights) {
170+
var maxArea = 0;
171+
var indexStack = new Stack<int>();
172+
heights = [0, ..heights, 0];
173+
174+
for (var i = 0; i < heights.Length; i++) {
175+
while (indexStack.Count > 0 && heights[i] < heights[indexStack.Peek()]) {
176+
var poppedIndex = indexStack.Pop();
177+
178+
var poppedHeight = heights[poppedIndex];
179+
var leftIndex = indexStack.Peek(); // poppedHeight's remaining left heights are all shorter than it, because when 'poppedHeight' itself was pushed into stack, it must have caused some (could be none) taller heights been popped out of the stack.
180+
var rightIndex = i; // poppedHeight's right heights (which are all taller than 'poppedHeight') have been popped out of the stack (disappeared) when current `i` height is being pushed into stack.
181+
var width = rightIndex - leftIndex - 1; // So in the range of 'width', they are all no shorter than `poppedHeight`, although they have been popped out of the stack (disappeared).
182+
183+
var area = poppedHeight * width;
184+
if (area > maxArea) {
185+
maxArea = area;
186+
}
187+
}
188+
189+
indexStack.Push(i);
190+
}
191+
192+
return maxArea;
193+
}
194+
}
195+
```
196+
197+
## Go
198+
```go
199+
func largestRectangleArea(heightSlice []int) int {
200+
maxArea := 0
201+
indexStack := []int{}
202+
heights := append([]int{0}, append(heightSlice, 0)...)
203+
204+
for i, height := range heights {
205+
for len(indexStack) > 0 && height < heights[indexStack[len(indexStack) - 1]] {
206+
poppedIndex := indexStack[len(indexStack) - 1]
207+
indexStack = indexStack[:len(indexStack) - 1]
208+
209+
poppedHeight := heights[poppedIndex]
210+
leftIndex := indexStack[len(indexStack) - 1] // poppedHeight's remaining left heights are all shorter than it, because when 'poppedHeight' itself was pushed into stack, it must have caused some (could be none) taller heights been popped out of the stack.
211+
rightIndex := i // poppedHeight's right heights (which are all taller than 'poppedHeight') have been popped out of the stack (disappeared) when current `i` height is being pushed into stack.
212+
width := rightIndex - leftIndex - 1 // So in the range of 'width', they are all no shorter than `poppedHeight`, although they have been popped out of the stack (disappeared).
213+
214+
area := poppedHeight * width
215+
if (area > maxArea) {
216+
maxArea = area
217+
}
218+
}
219+
220+
indexStack = append(indexStack, i)
221+
}
222+
223+
return maxArea
224+
}
225+
```
226+
227+
## Ruby
228+
```ruby
229+
def largest_rectangle_area(heights)
230+
heights = [0] + heights + [0]
231+
max_area = 0
232+
index_stack = []
233+
234+
heights.each_with_index do |height, i|
235+
while !index_stack.empty? && height < heights[index_stack.last]
236+
popped_index = index_stack.pop
237+
238+
popped_height = heights[popped_index]
239+
240+
left_index = index_stack[-1] # popped_height's remaining left heights are all shorter than 'popped_height', because when 'popped_height' itself was pushed into stack, it must have caused some (could be none) taller heights been popped out of the stack.
241+
right_index = i # popped_height's right heights (which are all taller than 'popped_height') have been popped out of the stack (disappeared) when current `i` height is being pushed into stack.
242+
width = right_index - left_index - 1 # So in the range of 'width', they are all no shorter than `popped_height`, although they have been popped out of the stack (disappeared).
243+
244+
area = popped_height * width
245+
max_area = area if area > max_area
246+
end
247+
248+
index_stack << i
249+
end
250+
251+
max_area
252+
end
253+
```
254+
255+
## Rust
256+
```rust
257+
// Welcome to create a PR to complete the code of this language, thanks!
258+
```
259+
260+
## Other languages
261+
```
262+
// Welcome to create a PR to complete the code of this language, thanks!
263+
```

0 commit comments

Comments
 (0)