Java LeetCode刷题 单调栈

单调栈

概念

单调栈（Monotonic Stack）是一个特殊的数据结构，它是一种栈，但具有单调性的特性。单调栈有两种类型：单调递增栈和单调递减栈。

在单调递增栈中，栈内的元素保持递增顺序，即后入栈的元素总是大于或等于先入栈的元素。同样，在单调递减栈中，栈内的元素保持递减顺序，即后入栈的元素总是小于或等于先入栈的元素。

以下是一个单调栈的基本实现（以单调递减栈为例）：

def monotone_stack(nums):  
    stack = []  
    result = [-1] * len(nums)  
    for i in range(len(nums)):  
        while stack and nums[i] < nums[stack[-1]]:  
            # 出栈，并记录右边第一个比其小的元素的下标  
            result[stack.pop()] = i  
        stack.append(i)  
    # 处理剩余栈内元素  
    while stack:  
        result[stack.pop()] = len(nums)  
    return result

这个函数会返回一个列表，表示每个元素的右边第一个比其小的元素的下标。如果没有这样的元素，则返回数组长度（表示该元素右边没有其他元素）。注意，这个实现是针对单调递减栈的，如果需要单调递增栈，只需将比较符号从 < 改为 > 即可。

举个例子，对于输入数组 [5, 3, 1, 4, 2]，单调递减栈的输出为 [4, 2, 1, 5, -1]。这表示：

• 数字 5 右边第一个比它小的数字是 4（下标为 3）
• 数字 3 右边第一个比它小的数字是 2（下标为 4）
• 数字 1 右边没有比它小的数字（下标为 -1）
• 数字 4 右边第一个比它小的数字是 2（下标为 4），但实际上这个输出是不准确的，因为数字 2 在数字 4 的左边。这里我们可以看到，这个实现其实是在找右边第一个比其小的元素，而不是左边。
• 数字 2 右边没有比它小的数字（下标为 -1）

注意，上述例子的输出描述有误。实际上，对于输入数组 [5, 3, 1, 4, 2]，正确的输出应该是每个元素的右边第一个比其大的元素的下标。为了得到左边第一个比其大的元素的下标，我们需要稍微修改一下算法。

这是一个更准确的描述和示例，展示如何使用单调栈找到每个元素左边第一个比其大的元素的位置：

def monotone_stack(nums):
    stack = []
    result = [-1] * len(nums)  # 初始化结果列表，所有位置先设为-1
    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            # 当前元素比栈顶元素大，所以栈顶元素的左边第一个比它大的元素就是当前元素
            result[stack.pop()] = i
        stack.append(i)  # 将当前元素下标入栈
    return result

# 示例
nums = [5, 3, 1, 4, 2]
print(monotone_stack(nums))  # 输出: [-1, 0, -1, 0, 3]

在这个修正后的示例中：

• 数字 5 左边没有比它大的数字（下标为 -1）
• 数字 3 左边第一个比它大的数字是 5（下标为 0）
• 数字 1 左边没有比它大的数字（下标为 -1）
• 数字 4 左边第一个比它大的数字是 5（下标为 0），注意这里不是 3，因为我们要找的是比 4 大的数字
• 数字 2 左边第一个比它大的数字是 4（下标为 3）

这样，我们就得到了每个元素左边第一个比其大的元素的位置。

每日温度

https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked

public static int[] dailyTemperatures(int[] temperatures){ // 栈一直单调递减
        int n = temperatures.length;
        int[] res = new int[n];

        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = temperatures.length - 1; i >= 0; i--) {
            int t = temperatures[i];
            while (!stack.isEmpty() && t>=temperatures[stack.peek()]){// 有比之前大的数字就弹出去
                stack.pop();
            }

            if(!stack.isEmpty()){
                res[i] = stack.peek()-i;
            }

            stack.push(i);
        }

        return res;

    }