739. 每日温度
题目
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
答案
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Stack<Integer> stack = new Stack();
for(int i=0;i<temperatures.length;i++){
while(!stack.isEmpty() && temperatures[i]>temperatures[stack.peek()]){
int index = stack.pop();
res[index] = i - index;
}
stack.push(i);
}
return res;
}
}
496. 下一个更大元素 I
题目
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
答案
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] res = new int[nums1.length];
Map<Integer,Integer> map = new HashMap();
Stack<Integer> stack = new Stack();
for(int i=0;i<nums1.length;i++){
map.put(nums1[i],i);
res[i] = -1;
}
for(int i=0;i<nums2.length;i++){
while(!stack.isEmpty() && nums2[i]>nums2[stack.peek()]){
int index = stack.pop();
if(map.containsKey(nums2[index])){
res[map.get(nums2[index])] = nums2[i];
}
}
stack.push(i);
}
return res;
}
}
503. 下一个更大元素 II
题目
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]
答案
class Solution {
public int[] nextGreaterElements(int[] nums) {
int len = nums.length;
int[] res = new int[len];
Stack<Integer> stack = new Stack();
for(int i=0;i<len;i++){
res[i] = -1;
}
for(int i=0;i<2*len;i++){
while(!stack.isEmpty() && nums[i%len]>nums[stack.peek()]){
int index = stack.pop();
res[index] = nums[i%len];
}
stack.push(i%len);
}
return res;
}
}
42. 接雨水
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
答案
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length-1;
int leftMax = 0, rightMax = 0;
int res = 0;
while(left<right){
leftMax = Math.max(leftMax,height[left]);
rightMax = Math.max(rightMax,height[right]);
if(height[left]<height[right]){
res += leftMax - height[left++];
}else{
res += rightMax - height[right--];
}
}
return res;
}
}
84. 柱状图中最大的矩形
题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
答案
class Solution {
public int largestRectangleArea(int[] heights) {
int[] newHeight = new int[heights.length+2];
for(int i=0;i<heights.length;i++){
newHeight[i+1] = heights[i];
}
newHeight[0] = 0;
newHeight[newHeight.length-1] = 0;
int res = 0;
Stack<Integer> stack = new Stack();
for(int i=0;i<newHeight.length;i++){
while(!stack.isEmpty() && newHeight[i]<newHeight[stack.peek()]){
int mid = stack.pop();
int with = i - stack.peek() - 1;
int heigh = newHeight[mid];
res = Math.max(res,with*heigh);
}
stack.push(i);
}
return res;
}
}
