【算法刷题day60】Leetcode：84. 柱状图中最大的矩形

草稿图网站
java的Deque

Leetcode 84. 柱状图中最大的矩形

题目：84. 柱状图中最大的矩形
解析：代码随想录解析

解题思路

反方向接雨水。见上一篇文章

代码

class Solution {public int largestRectangleArea(int[] heights) {int[] newHeights = new int[heights.length+2];System.arraycopy(heights, 0, newHeights, 1, heights.length);int res = 0;Stack<Integer> stack = new Stack<>();stack.push(0);for (int i = 1; i < newHeights.length; i++) {if (newHeights[i] > newHeights[stack.peek()]) stack.push(i);else if (newHeights[i] == newHeights[stack.peek()]) {stack.pop();stack.push(i);} else {while (newHeights[i] < newHeights[stack.peek()]) {int mid = stack.peek();stack.pop();int left = stack.peek();int h = newHeights[mid];int w = i - left - 1;res = Math.max(res, w * h);}stack.push(i);}}return res;}
}//双指针
class Solution {public int largestRectangleArea(int[] heights) {int length = heights.length;int []leftHeight = new int[length];int []rightHeight = new int[length];leftHeight[0] = -1;for (int i = 1; i < length; i++) {int t = i-1;while (t >= 0 && heights[t] >= heights[i])t = leftHeight[t];leftHeight[i] = t;}rightHeight[length-1] = length;for (int i = length-2; i >= 0; i--) {int t = i+1;while (t < length && heights[t] >= heights[i])t = rightHeight[t];rightHeight[i] = t;}int res = 0;for (int i = 0; i < length; i++) {int area = (rightHeight[i] - leftHeight[i] - 1) * heights[i];res = Math.max(res, area);}return res;}
}

总结

暂无