Day 16。
今天两道题分别是 Longest Valid Parentheses 和 Search in Rotated Sorted Array。
一道是 括号匹配进阶题，一道是 二分查找变形题。

今天的关键词：栈、下标、有效区间、旋转数组、有序区间判断、二分变形。

🧠 LeetCode 32 – Longest Valid Parentheses

💡 思路总结

这题要求求出最长有效括号子串的长度。
和前面的“判断括号是否有效”不一样，这题不是简单判断 true/false，而是要找：

最长的那一段合法括号区间

你的做法是经典栈解法，而且很漂亮：

  • 栈里不存字符
  • 而是存 下标
  • 这样就能直接计算当前有效括号长度

这题的关键点就在这里：

用下标来表示“最近一个不能匹配的位置”

💻 代码实现

#include <stack>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> sta;//用栈来存储字符的地址，
        int result = 0;
        sta.push(-1);
        for(int i = 0 ; i < s.size();i++){
            if(s[i]=='('){
                sta.push(i);
            }
            else{
                sta.pop();
                if(sta.empty()){
                    sta.push(i);
                }
                else result = max(result,i-sta.top());
            }
        }
        return result;
    }
};

📌 知识点总结

1️⃣ 为什么栈里存的是下标

如果只存括号字符，其实你只能知道“能不能匹配”，但没法直接知道长度。

而存下标之后，一旦匹配成功，就能通过：

i - sta.top()

直接得到当前有效区间长度。

所以这题很关键的一步就是：

把匹配问题转化成区间长度问题

2️⃣ 为什么一开始要压入 -1

这一句是灵魂：

sta.push(-1);

它的作用可以理解成：

有效括号区间的左边界之前的位置

比如字符串是：

"()"

处理到右括号时，长度就是：

1 - (-1) = 2

如果没有这个 -1，很多从开头开始的合法区间就不好统一计算。

3️⃣ 遇到右括号时为什么先弹栈

当遇到 ')' 时，说明想拿它去匹配一个最近的 '('，所以先：

sta.pop();

如果弹完之后栈空了，说明当前这个右括号没有合法匹配对象，那就要把它自己的位置压进去：

sta.push(i);

意思是：

从这个位置开始，前面的区间已经断掉了

这个下标会成为后面新一段有效区间的“参考边界”。

4️⃣ 这题和 LeetCode 20 的区别

LeetCode 20 是：

  • 判断括号是否合法

而这题是：

  • 找最长合法子串长度

所以今天这题比 Day 10 更进一步。
同样用栈，但思路已经从“匹配判断”升级到了“区间长度计算”。

5️⃣ 这题还有别的做法

这题除了栈，还可以用：

  • 动态规划
  • 左右计数法

但栈法非常经典，也很直观。
对于当前阶段来说，这个解法已经非常值得掌握。

🔍 LeetCode 33 – Search in Rotated Sorted Array

💡 思路总结

这题要求在一个旋转后的升序数组中查找目标值。
数组原本有序，但被旋转了一次，比如：

[4,5,6,7,0,1,2]

虽然整体不再完全有序，但它有一个很重要的性质：

每次二分后，至少有一半仍然是有序的

你的做法就是围绕这个性质展开的：

  1. 先正常二分找 mid
  2. 判断左半边是否有序
  3. 如果左半边有序，判断目标是否在左半边范围里
  4. 否则看右半边是否有序，再判断目标是否在右半边

这就是这题最经典的思路。

💻 代码实现

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) return mid;

            // 左半边有序
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // 右半边有序
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
};

📌 知识点总结

1️⃣ 这题不是普通二分，是“二分变形”

普通二分默认整个数组有序。
但这题的数组被旋转了，所以不能直接比较目标和 mid 来决定方向。

必须先多做一步判断：

哪一半是有序的

这是这题最本质的区别。

2️⃣ 为什么一定有一半有序

旋转数组虽然整体断开了，但它本质上还是由两段升序数组拼起来的。

所以对于任意一个 mid，总能判断出：

  • 左边有序
  • 或者右边有序

这就是二分还能继续做下去的根本原因。

3️⃣ 判断左半边有序的条件

你这里写的是：

if (nums[left] <= nums[mid])

如果成立，就说明左边这段是升序的。

然后再看目标值是否落在：

[nums[left], nums[mid])

之间。

如果在，就往左边找；不在，就往右边找。

4️⃣ 右半边同理

如果左边不是有序的，那右边一定有序。

这时候就判断目标是否在：

(nums[mid], nums[right]]

之间。

如果在，往右找；否则往左找。

5️⃣ 这题训练的是“分类讨论能力”

这题代码不长，但很考验逻辑清晰度。
因为它不是一个公式一路写到底，而是不断在做判断：

  • 左边有序还是右边有序？
  • target 在这一半还是另一半？

所以这类题非常锻炼你对“二分条件分支”的掌控能力。

🧩 今日总结

题目核心思想
LeetCode 32栈存下标 + 有效括号区间长度计算
LeetCode 33旋转数组二分 + 判断哪一半有序

今天两题都不属于最基础模板了，而是经典模板的升级版：

  • 32 是栈匹配题的进阶
  • 33 是二分查找题的进阶

🧠 今日收获

今天最值得记住的两个模型：

1. 栈不一定存值，也可以存下标

当题目和“区间长度、位置关系、边界”有关时，栈里存下标往往更有用。

这题就是很典型的例子。

2. 二分不只是“有序数组里找值”

很多二分题的真正核心不是背模板，而是先判断：

  • 哪一部分满足单调性
  • 哪一部分还能继续二分

旋转数组这题，就是把“整体有序”变成了“局部有序”。

💬 写给自己的话

Day 16 了。

你现在已经不只是刷基础题了，
而是在不断接触这些“模板的变形题”。

这很重要。
因为真正拉开差距的，往往不是会不会最基础模板，
而是：

模板变一下，你还能不能认出来。

今天这两题就很典型：

  • 栈还是那个栈，但用途变了
  • 二分还是那个二分，但条件变了

而你现在就在慢慢适应这种变化。

继续坚持。
别怕题目开始变形，这正是你从“会做题”走向“会分析题”的过程。

阿玉，Day 16，继续冲。

—— 刷题第 16 天