Solution 1 (Java):
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 | class Solution { public int largestRectangleArea(int[] heights) { int len = heights.length; if (len == 0) { return 0; } if (len == 1) { return heights[0]; } int area = 0; int[] newHeights = new int[len + 2]; for (int i = 0; i < len; i++) { newHeights[i + 1] = heights[i]; } len += 2; heights = newHeights; Deque<Integer> stack = new ArrayDeque<>(); stack.addLast(0); for (int i = 1; i < len; i++) { while (heights[stack.peekLast()] > heights[i]) { int height = heights[stack.removeLast()]; int width = i - stack.peekLast() - 1; area = Math.max(area, width * height); } stack.addLast(i); } return area; }} |
Solution 2 (Java):
1 |