LeetCode 456. 132 模式

Categories:

题目描述
思路分析
1. 解法一：单调栈（从右往左）（推荐）
相似题目

题目描述

✅ 456. 132 模式

思路分析

解法一：单调栈（从右往左）（推荐）

核心思路：

从右向左扫描，用单调递减栈维护候选的 “3”。

变量 third 记录当前可用的最大 “2”。

若遇到 nums[i] < third，说明存在 132 模式。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，其中 n 表示栈的大小。

import java.util.*;

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        int third = Integer.MIN_VALUE;
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < third) {
                return true;
            }

            // 维护单调递减栈，弹出比当前值小的元素更新 third
            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                third = stack.pop();
            }

            stack.push(nums[i]);
        }

        return false;
    }
}

func find132pattern(nums []int) bool {
	third := -1 << 60
	stack := make([]int, 0)

	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] < third {
			return true
		}

		// 维护单调递减栈，弹出比当前值小的元素更新 third
		for len(stack) > 0 && nums[i] > stack[len(stack)-1] {
			third = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
		}

		stack = append(stack, nums[i])
	}

	return false
}

相似题目

题目	难度	考察点
496. 下一个更大元素 I	简单	单调栈
503. 下一个更大元素 II	中等	单调栈
739. 每日温度	中等	单调栈
84. 柱状图中最大的矩形	困难	单调栈
402. 移掉 K 位数字	中等	单调栈、贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/35191906