Let's go through it with the example shown in the graph.
Since i will also serve a row as the width of the rectangle, the iteration should go from 0 to the height.length.
i = 0, stack is empty, stack.push(0).
i = 1, curr < height[0], max = the area of rectangle 0, stack.push(1).
from i = 2 to 4, the height of the rectangle is increasing, the largest rectangle may be height[1] * 5 height[2] * 4 ... height[4] * 1, we store i -s in the stack.
i = 5, now curr (height[5]) < height[4], we calculate the area of each rectangle and find the maximum.
Note i = 1 is still in the stack because it is smaller than curr, which means it may form larger rectangle with next several rectangles (e.g., the red rectangle when i = 6).
When i = 7, since we want to count the last rectangle, we assume curr = -1 which is always smaller than any height[i].
public class MaxRectangle { public int largestRectangleArea(int[] height) { if (height == null || height.length == 0) return 0; Stackstack = new Stack (); int max = 0; for (int i = 0; i <= height.length; i++) { int curr = (i == height.length) ? -1 : height[i]; while (!stack.isEmpty() && curr <= height[stack.peek()]) { int h = height[stack.pop()]; // last element in the stack is the rectangle with the shortest height, thus the area of rectangle is // i * height int w = stack.isEmpty() ? i : i - stack.peek() - 1; max = Math.max(max, h * w); } stack.push(i); } return max; } }
No comments:
Post a Comment