惠州网站建设网站,应该符合建设网站,郏县网站制作公司,wordpress迁移安装503. 下一个更大元素 II
中等 给定一个循环数组 nums #xff08; nums[nums.length - 1] 的下一个元素是 nums[0] #xff09;#xff0c;返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序#xff0c;这个数字之后的第一个比它更…503. 下一个更大元素 II
中等 给定一个循环数组 nums nums[nums.length - 1] 的下一个元素是 nums[0] 返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出 -1 。
思路
一开始我也想的用俩数组拼然后用单调栈的方法
// 这个也是遍历两遍nums数组只是省了点空间
class Solution {public int[] nextGreaterElements(int[] nums) {int len nums.length;int[] res new int[len];Arrays.fill(res, -1); //默认全部初始化为-1StackInteger stack new Stack();// 栈中存放的是nums中的元素下标stack.add(0);// 模拟遍历两遍nums注意一下都是用i % nums.size()来操作for (int i 1; i 2 * len; i) {if (nums[i % len] nums[stack.peek()]) { // 当前元素小于等于栈顶元素入栈stack.add(i % len); // 入栈的是索引索引是不可能大于len的} else { // 当前元素大于栈顶元素弹出while(!stack.isEmpty() nums[i % len] nums[stack.peek()]) {res[stack.peek()] nums[i % len];stack.pop();}stack.add(i % len);}}return res;}
}42. 接雨水
困难 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水
思路:
黑色的看成墙蓝色的看成水宽度一样给定一个数组每个数代表从左到右墙的高度求出能装多少单位的水。也就是图中蓝色正方形的个数.
// 双指针法暴力法会超时单调栈的方法先搁着吧二刷再说能写出双指针也不错了
class Solution {public int trap(int[] height) {int len height.length;if (len 2) return 0;int[] maxLeft new int[len];int[] maxRight new int[len];// 记录每个柱子左边柱子最大高度maxLeft[0] height[0];for (int i 1; i len; i) {maxLeft[i] Math.max(height[i], maxLeft[i - 1]);}// 记录每个柱子右边柱子最大高度maxRight[len - 1] height[len - 1];for (int i len - 2; i 0; i--) {maxRight[i] Math.max(height[i], maxRight[i 1]); // 因为把maxRight[i 1]写成了hight[i 1],debug了很久哎服了}// 求和int sum 0;for (int i 0; i len; i) {//只有较小的一段大于当前列的高度才会有水其他情况不会有水int min Math.min(maxLeft[i], maxRight[i]);if (min height[i]) {sum (min - height[i]);}} return sum;}
}
