-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
36 lines (35 loc) · 964 Bytes
/
Solution.cs
File metadata and controls
36 lines (35 loc) · 964 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution
{
public int LargestRectangleArea(int[] heights)
{
int n = heights.Length;
int max = 0;
Stack<(int w, int h)> stack = [];
int tmpW, tmpH;
for (int i = 0; i < n; i++)
{
tmpW = 0;
tmpH = int.MaxValue;
max = Math.Max(max, heights[i]);
while (stack.Count > 0 && stack.Peek().h >= heights[i])
{
var (w, h) = stack.Pop();
tmpW += w;
tmpH = Math.Min(tmpH, h);
max = Math.Max(max, tmpW * tmpH);
}
stack.Push((tmpW, tmpH));
stack.Push((1, heights[i]));
}
tmpW = 0;
tmpH = int.MaxValue;
while (stack.Count > 0)
{
var (w, h) = stack.Pop();
tmpW += w;
tmpH = Math.Min(tmpH, h);
max = Math.Max(max, tmpW * tmpH);
}
return max;
}
}