Java算法真题详解运用单调栈

Java算法真题详解运用单调栈攻略

1. 什么是单调栈

单调栈是指栈中元素单调递增或递减的栈。

单调栈在算法中的应用比较广泛，经常用来解决类似于比当前数大的第一个数、比当前数小的第一个数等等问题。

2. 单调栈解法

单调栈的解法分为两类：单调递增栈和单调递减栈。具体的应用方式如下：

2.1. 单调递增栈

单调递增栈指栈中元素单调递增，栈底元素最小。

单调递增栈的应用场景：

• 求某个数右侧第一个比它大的数/位置
• 求某个数左侧第一个比它大的数/位置

示例：对于数组 nums=[4,3,5,2,1,6]，求每个数右侧第一个比它大的数。

代码实现：

public int[] nextGreaterElement(int[] nums) {
    int n=nums.length;
    int[] res=new int[n];
    Arrays.fill(res,-1);  // 先将结果数组都赋值为-1
    Deque<Integer> stack=new LinkedList<>();  // 定义单调递增栈

    for(int i=0;i<n;i++){
        // 栈不为空且当前数大于栈顶元素，则出栈并记录答案
        while(!stack.isEmpty()&&nums[stack.peek()]<nums[i]){
            res[stack.pop()]=nums[i];
        }
        stack.push(i);  // 当前数入栈
    }
    return res;
}

上述代码中，我们使用一个栈来存储每个数的下标。从左往右遍历数组，对于每个数，我们不断地弹出栈顶元素并更新答案，直到当前数的大小大于栈顶元素。最后，我们将当前数入栈。

2.2. 单调递减栈

单调递减栈指栈中元素单调递减，栈底元素最大。

单调递减栈的应用场景：

• 求某个数左侧第一个比它小的数/位置
• 求某个数右侧第一个比它小的数/位置

示例：对于数组 nums=[4,3,5,2,1,6]，求每个数左侧第一个比它小的数。

代码实现：

public int[] nextSmallerElement(int[] nums) {
    int n=nums.length;
    int[] res=new int[n];
    Arrays.fill(res,-1);  // 先将结果数组都赋值为-1
    Deque<Integer> stack=new LinkedList<>();  // 定义单调递减栈

    for(int i=n-1;i>=0;i--){
        // 栈不为空且当前数小于栈顶元素，则出栈并记录答案
        while(!stack.isEmpty()&&nums[stack.peek()]>nums[i]){
            res[stack.pop()]=nums[i];
        }
        stack.push(i);  // 当前数入栈
    }
    return res;
}

上述代码与单调递增栈类似，只是从右往左遍历数组，同时使用单调递减栈。

3. 总结

单调栈是一个非常实用的算法，能够有效地解决一些问题。在本文中，我们介绍了单调递增栈和单调递减栈的应用，并给出了示例说明。希望本文能够帮助到大家。