网站建设类的公司名怎么起,做啥英文网站赚钱,网站开发主要包括的事项,团购网站为什么做不走一、LeetCode503. 下一个更大元素 II
题目链接#xff1a;503. 下一个更大元素 II
题目描述#xff1a;
给定一个循环数组 nums #xff08; nums[nums.length - 1] 的下一个元素是 nums[0] #xff09;#xff0c;返回 nums 中每个元素的 下一个更大元素 。
数字 x 的…一、LeetCode503. 下一个更大元素 II
题目链接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]提示:
1 nums.length 104-109 nums[i] 109
算法分析
这道题跟739. 每日温度差不多只不过需要遍历两次nums相当于将nums看成一个环。
代码如下
class Solution {public int[] nextGreaterElements(int[] nums) {int len nums.length;StackIntegerst new Stack();int[] answer new int[len];//用来记录nums中每个元素的下一个更大元素Arrays.fill(answer, -1);//用-1初始化for(int i 0; i len * 2; i) {//遍历两次numswhile(!st.isEmpty() nums[i % len] nums[st.peek()]){answer[st.pop()] nums[i % len];}st.push(i % len);}return answer;}
}
二、LeetCode42. 接雨水
题目链接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提示
n height.length1 n 2 * 1040 height[i] 105
算法分析
用一张单调栈来存放没有出现过下一个更高柱子的柱子高度等出现高柱子时就可以求出它与它前面第一个比它高或者相等的柱子之间所形成的凹槽面积。
代码如下
class Solution {public int trap(int[] height) {int len height.length;int sum 0;//用来记录可接受的雨水体积StackIntegerst new Stack();for(int i 0; i len; i) {while(!st.isEmpty() height[i] height[st.peek()]) {int mid st.pop();//记录凹槽的底部高度不一定是两边之间最低的那一个if(!st.isEmpty()) {int l Math.min(height[i],height[st.peek()]) - height[mid];//两边的高度取最小值然后减去底部高度就是可以增加的雨水高度int w i - st.peek() - 1;//可以增加的雨水宽度sum l * w;}}st.push(i);}return sum;}
}
总结
第二题是比较难的
