2023.12.12力扣每日一题

2023-12-16 11:25:27

题目来源

力扣每日一题;题序:2454

我的题解

方法一

暴力解法。就双重循环,找到第二个比当前值大的元素,找不到则置为-1,并且末尾两个位置一定是找不到的,因此不在遍历

时间复杂度:O(n^2)
空间复杂度:O(1)。不包含结果所占空间

class Solution {
    public int[] secondGreaterElement(int[] nums) {
        int n=nums.length;
        int[] res=new int[n];
        Arrays.fill(res,-1);
        for(int i=0;i<n-2;i++){
            int temp=-1;
            int count=0;
            for(int j=i+1;j<n;j++){
                if(nums[j]>nums[i]){
                    count++;
                }
                if(count==2){
                    temp=nums[j];
                    break;
                }
            }
            res[i]=temp;
        }
        return res;
    }
}
方法二 单调栈+最小堆

这道题实际是对于求下一个更大元素问题的升级,因此我们可以先求出每个下标的下一个更大元素。所以使用一个最小堆存储下一个更大元素,利用单调栈找当前最大值。
步骤:

  1. 若该 最小堆 非空且堆顶元素小于当前遍历的元素时,说明当前元素为堆顶元素的「第二大」的整数,我们取出堆顶元素,并更新结果数组。重复该操作直至 最小堆 为空或者堆顶元素大于等于当前遍历元素。
  2. 若 单调栈 非空且栈顶元素对应的值小于当前遍历元素,则说明找到了栈顶元素的下一个更大的数字,将栈顶元素出栈,并加入堆中。重复执行该操作直至 栈为空或者栈顶元素大于等于当前遍历元素。
    将当前元素的下标压入栈 中

时间复杂度:O(n×logn)
空间复杂度:O(n)

class Solution {
    public int[] secondGreaterElement(int[] nums) {
        int n=nums.length;
        int[] res=new int[n];
        Arrays.fill(res,-1);
        Deque<Integer> stack=new LinkedList<>();
        // [下一个更大元素值,下一个更大元素下标]
        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]-b[0]);
        for(int i=0;i<n;i++){
        	// 得到第二大整数
            while(!pq.isEmpty()&&pq.peek()[0]<nums[i]){
                res[pq.poll()[1]]=nums[i];
            }
            //记录下一个更大元素
            while(!stack.isEmpty()&&nums[stack.peek()]<nums[i]){
                pq.offer(new int[]{nums[stack.peek()],stack.peek()});
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }
}
方法三 单调增栈+单调减栈

在方法二中,在执行操作 1 后,如果最小堆非空,则堆顶元素一定大于等于当前遍历元素。同时,在操作 2 中,从单调栈中弹出的元素一定满足小于当前遍历元素的条件。因此,从单调栈中弹出的元素一定小于堆顶元素(如果堆非空)。可以进一步优化「方法二」的时间复杂度,用另一个「单调递减栈」
具体步骤:

  1. 若该 单调减栈 非空且栈顶元素小于当前遍历的元素时,说明当前元素为栈顶元素的「第二大」的整数,将栈顶元素出栈,并更新结果数组。重复该操作直至 单调减栈 为空或者栈顶元素大于等于当前遍历元素。
  2. 若 单调增栈 非空且栈顶元素对应的值小于当前遍历元素,则说明找到了栈顶元素的下一个更大的数字,将栈顶元素出栈。重复执行该操作直至 单调增栈 为空或者栈顶元素大于等于当前遍历元素。然后我们将出栈的元素按照在 单调增栈 中的顺序加入 单调减栈 中。
  3. 将当前元素的下标压入 单调增栈 中。

时间复杂度:O(n)
空间复杂度:O(n)

class Solution {
    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        List<Integer> stack1 = new ArrayList<Integer>();
        List<Integer> stack2 = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!stack2.isEmpty() && nums[stack2.get(stack2.size() - 1)] < nums[i]) {
                res[stack2.get(stack2.size() - 1)] = nums[i];
                stack2.remove(stack2.size() - 1);
            }
            int pos = stack1.size() - 1;
            while (pos >= 0 && nums[stack1.get(pos)] < nums[i]) {
                --pos;
            }
            for (int j = pos + 1; j < stack1.size(); j++) {
                stack2.add(stack1.get(j));
            }
            for (int j = stack1.size() - 1; j >= pos + 1; j--) {
                stack1.remove(j);
            }
            stack1.add(i);
        }
        return res;
    }
}

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

文章来源:https://blog.csdn.net/weixin_42075274/article/details/134954593
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。