classSolution{ publicintlargestRectangleArea(int[] heights){ Deque<Integer> stack = new LinkedList<>(); int[] newHeights = newint[heights.length + 2]; for (int i = 1; i < newHeights.length - 1; i++) { newHeights[i] = heights[i - 1]; } int res = 0; for (int i = 0; i < newHeights.length; i++) { while (!stack.isEmpty() && newHeights[stack.peek()] > newHeights[i]) { int current = stack.pop(); res = Math.max(res, (i-stack.peek()-1)*newHeights[current]); } stack.push(i); } return res; } }
lc739 每日温度
这就是最本质的单调栈应用,没有变体,题目要求就是找到每个元素右边第一个比它大的元素。
那直接用单调减的栈,如果当前元素大于栈顶,则对于栈顶的元素就是找到了,直接出栈,更新就好。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution{ publicint[] dailyTemperatures(int[] temperatures) { Deque<Integer> st = new LinkedList<>(); int[] res = newint[temperatures.length]; for (int i = 0; i < temperatures.length; i++) { while (!st.isEmpty() && temperatures[st.peek()] < temperatures[i]) { int current = st.pop(); res[current] = i - current; } st.push(i); } return res; } }