网站开发 家具销售 文献,租号网站开发成本,网站建设工作室深圳,焦作电子商务网站建设实例目录 下一个更大元素II接雨水 LeetCode 503.下一个更大元素II LeetCode 42. 接雨水
下一个更大元素II
给定一个循环数组 nums #xff08; nums[nums.length - 1] 的下一个元素是 nums[0] #xff09;#xff0c;返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一… 目录 下一个更大元素II接雨水 LeetCode 503.下一个更大元素II LeetCode 42. 接雨水
下一个更大元素II
给定一个循环数组 nums nums[nums.length - 1] 的下一个元素是 nums[0] 返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出 -1 。
问题的关键在于在遍历的过程中模拟走了两遍 nums
class Solution {public int[] nextGreaterElements(int[] nums) {DequeInteger stack new LinkedList();int[] res new int[nums.length];Arrays.fill(res, -1);stack.push(0);int length nums.length;for (int i 0; i length * 2; i) { while (!stack.isEmpty() nums[i % length] nums[stack.peek()]) {res[stack.peek()] nums[i % length];stack.pop();}stack.push(i % length);}return res;}
}接雨水
暴力 也是使用双指针。按照列来计算的话宽度一定是1了我们再把每一列的雨水的高度求出来就可以了。只要记录左边柱子的最高高度 和 右边柱子的最高高度就可以计算当前位置的雨水面积这就是通过列来计算。当前列雨水面积min(左边柱子的最高高度记录右边柱子的最高高度) - 当前柱子高度。 min(lHeight, rHeight) - height。只要从头遍历一遍所有的列然后求出每一列雨水的体积相加之后就是总雨水的体积了。时间复杂度为 O ( n 2 ) O(n^2) O(n2)空间复杂度为 O ( 1 ) O(1) O(1)。 超时 class Solution {public int trap(int[] height) {// 暴力int sum 0;for (int i 0; i height.length; i) {// 第一个柱子和最后一个柱子不接水if(i 0 || i height.length - 1) continue;int rHeight height[i]; // 记录右边柱子的最高高度int lHeight height[i]; // 记录左边柱子的最高高度for (int r i 1; r height.length; r){rHeight Math.max(rHeight, height[r]);}for (int l i - 1; l 0; l--){lHeight Math.max(lHeight, height[l]);}int h Math.min(rHeight, lHeight) - height[i];if (h 0) sum h;}return sum;}
}双指针优化 优化思路是讲取左侧最高高度和右侧最高高度脱离出来提前处理暴力解法中为了得到两边的最高高度使用了双指针来遍历每到一个柱子都向两边遍历一遍这其实是有重复计算的。我们把每一个位置的左边最高高度记录在一个数组上maxLeft右边最高高度记录在一个数组上maxRight这样就避免了重复计算。从左向右遍历maxLeft[i] max(height[i], maxLeft[i - 1]);从右向左遍历maxRight[i] max(height[i], maxRight[i 1]);
class Solution {public int trap(int[] height) {// 双指针优化if (height.length 2) return 0;int[] maxLeft new int[height.length];int[] maxRight new int[height.length];int length height.length;// 记录每个柱子左边柱子的最大高度maxLeft[0] height[0];for (int i 1; i length; i) {maxLeft[i] Math.max(height[i], maxLeft[i-1]);}// 记录每个柱子右边柱子的最大高度maxRight[length-1] height[length-1];for (int i length-2; i 0; i--) {maxRight[i] Math.max(height[i], maxRight[i1]);}// 求和int sum 0;for (int i 0; i length; i) {int count Math.min(maxLeft[i], maxRight[i]) - height[i];if (count 0) sum count;}return sum;}
}单调栈 单调栈就是保持栈内元素有序需要自己维持顺序。通常是一维数组要寻找任一个元素的右边或左边第一个比自己大或者小的元素的位置此时用单调栈。 class Solution {public int trap(int[] height) {if (height.length 2) return 0;StackInteger stack new StackInteger();stack.push(0);int sum 0;for (int i 1; i height.length; i) {if (height[i] height[stack.peek()]) {stack.push(i);}else if (height[i] height[stack.peek()]) {stack.pop();stack.push(i);}else {// pop up all lower valuewhile (!stack.isEmpty() height[i] height[stack.peek()]) {int mid stack.peek();stack.pop();if (!stack.isEmpty()) {int h Math.min(height[stack.peek()], height[i]) - height[mid];int w i - stack.peek() - 1;int hold h * w;if (hold 0) sum hold;}}stack.push(i);}}return sum;}
}
