代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I

简介: 代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I

代码随想录算法训练营第五十九天 | LeetCode 503. 下一个更大元素 II、42. 接雨水

1. LeetCode 503. 下一个更大元素 II

1.1 思路

  1. 本题是给一个数组求右边第一个比当前元素大的元素,好像和739. 每日温度差不多,但本题多了个循环数组的要求,首尾是相连的
  2. 思路 1:建立一个新数组,把原数组扩充一倍再放入这个新数组中,即这个新数组的长度是原数组的 2 倍,然后线性遍历求当前元素右边第一个比其大的元素,这样就不用循环数组了,最后返回一半数组即可。这么写就是空间复杂度就是创建了一个 2 倍的数组,时间复杂度就是 O(n)
  3. 思路 2:在原数组模拟循环的方式,通过取模的方式。遍历数组时还是通过 2 倍数组来遍历,for(int i=0;i<nums.length*2;i++),如果直接取 i,当超过 nums.length 时就会越界,因此 i=i%nums.length,这样当超出范围时一取模就又回来了。
  4. 单调栈的模板代码:result 数组存储结果,注意要将数组默认初始化为全-1 的值,因为本题找不到存的是-1,然后定义个栈,把 0 下标先放入 stack.push(0)。for(int i=1;i<nums.length*2;i++)从 1 开始是因为 0 下标已经存入。避免 i 越界,i=i%nums.length;if(nums[i]<=nums[stack.peek()])stack.push(i);else while(!stack.empty()&&nums[i]>nums[stack.peek()])result[stack.peek()]=nums[i],stack.pop();while 循环结束后 stack.push(i)。最终 return result。

1.2 代码

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        //边界判断
        if(nums == null || nums.length <= 1) {
            return new int[]{-1};
        }
        int size = nums.length;
        int[] result = new int[size];//存放结果
        Arrays.fill(result,-1);//默认全部初始化为-1
        Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标
        for(int i = 0; i < 2*size; i++) {
            while(!st.empty() && nums[i % size] > nums[st.peek()]) {
                result[st.peek()] = nums[i % size];//更新result
                st.pop();//弹出栈顶
            }
            st.push(i % size);
        }
        return result;
    }
}

2. LeetCode 42. 接雨水

2.1 思路

  1. 本题是给一个 height 数组“接雨水”,因为这些数组的元素形成柱子就会有一些凹槽,就能存些雨水,最后就返回能接多少岁雨水。
  2. 引出单调栈:单调栈适用于找到左边或者右边第一个比当前元素大的元素。本题的栈是递增还是递减呢?本题中我们不仅要求右边第一个比其大的元素,还要求左边第一个比其大的元素,因为要找到凹槽嘛,而我们确定一个凹槽就是要左右两边的柱子顶起来,中间有个底托起来
  3. 本题单调栈的工作过程是当前元素和栈顶元素比较,本题中如果当前元素大于栈顶元素那就是右边第一个比其大的元素,此时栈顶元素就是底了,右边的柱子也找到了,就差左边的柱子了,其实就在栈里,就是栈顶的下一个元素,这个就是左边第一个比其大的元素。
  4. 当前元素和栈顶元素的比较就大于等于小于三种情况。本题中,小于仍然是放入栈中;等于也是放入栈中,也可以把栈顶弹出再将但当前元素放入,其实都可以,但我们选择前者,这两个的区别就是计算有点差异而已;大于时,此时栈顶就是底,当前元素就是右边的柱子,左边的柱子就是栈顶下一个元素。
  5. 计算过程:底=stack.pop();柱子的高度要取最小值,因为取高的部分会漏出去,想象一下凹槽存水的原理木桶效应就知道了,h=Math.min(stack.peek(),height[i]),然后 h 减去 底的高度差就是存水的高度,凹槽的宽度就是右柱子的下标减去左柱子的下标,即 w=i-stack.peek()-1,为什么需要减 1,举例右柱子 4 下标,左柱子 2 下标,宽度应该是 1,求的就是中间凹槽的宽度,因此要-1。h*w 就是面积。因为栈顶前面弹出了,当前元素仍有可能比栈顶大,因此还能确定凹槽,因此用 while 循环遍历。前面说等于时是把当前元素直接放入还是先弹出再放入当前元素的时候,说的是都可以是因为,如果放入此时的最矮柱子和底的高度差是 0,面积也是 0,而如果弹出再放入就是少算了这个 0,因此没区别。
  6. 单调栈求面积是横向求的,而暴力是纵向求的。
  7. 代码实现:定义 sum 存面积,定义栈然后放入 0 下标,for(int i=1;i<height.length;i++)从 1 开始是因为 0 下标已经放入。if(height[i]<=height[stack.peek()])stack.push(i);else while(!stack.empty()&&heigth[i]>height[stack.peek()])int middle=stack.pop()这是底,if(!stack.empty())这里要判断一下不能为空栈,h=Math.min(height[stack.peek()],height[i])-height[mid] 这是高度差,w=i-stack.peek()-1 这是宽度;sum+=h*w。当 while 循环结束了也把当前元素放入栈中。最终 return sum。

2.2 代码

class Solution {
    public int trap(int[] height){
        int size = height.length;

        if (size <= 2) return 0;

        // in the stack, we push the index of array
        // using height[] to access the real height
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);

        int sum = 0;
        for (int index = 1; index < size; index++){
            int stackTop = stack.peek();
            if (height[index] < height[stackTop]){
                stack.push(index);
            }else if (height[index] == height[stackTop]){
                // 因为相等的相邻墙,左边一个是不可能存放雨水的,所以pop左边的index, push当前的index
                stack.pop();
                stack.push(index);
            }else{
                //pop up all lower value
                int heightAtIdx = height[index];
                while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){
                    int mid = stack.pop();

                    if (!stack.isEmpty()){
                        int left = stack.peek();

                        int h = Math.min(height[left], height[index]) - height[mid];
                        int w = index - left - 1;
                        int hold = h * w;
                        if (hold > 0) sum += hold;
                        stackTop = stack.peek();
                    }
                }
                stack.push(index);
            }
        }

        return sum;
    }
}


目录
打赏
0
1
1
0
9
分享
相关文章
|
4月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
53 1
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
86 3
|
4月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
53 0
|
4月前
|
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
92 4
|
4月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
42 0
|
4月前
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
40 0
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等