数据结构与算法之栈结构

栈

• 特性：先进后出
• 解题法则：
  • 题目中有配对、消除的题意，优先考虑栈结构
  • 栈中存放的可以是内容本身和内容的索引
  • 数组中右边第一个比我小的元素的位置，求解用递增栈
  • 较小的数消除掉较大的数的时候，使用递增栈。
  • 根据题意总结入栈与出栈的时机

普通栈

• 规律性：配对、消除

---

• 例题1：字符串中只有字符’(‘和’)’。合法字符串需要括号可以配对。比如：
  输入：”()”
  输出：true
  解释：()，()()，(())是合法的。)(，()(，(()是非法的。
  请你实现一个函数isValid(s)，来判断给定的字符串是否合法。

  针对例1这种内容一样时，可以使用计数器优化

• 例题拓展： 给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：
  左括号必须用相同类型的右括号闭合
  左括号必须以正确的顺序闭合
  注意空字符串可被认为是有效字符串
  请实现isValid(s)

---

• 例题2：在水中有许多鱼，可以认为这些鱼停放在 x 轴上。再给定两个数组 Size，Dir，Size[i] 表示第 i 条鱼的大小，Dir[i] 表示鱼的方向 （0 表示向左游，1 表示向右游）。这两个数组分别表示鱼的大小和游动的方向，并且两个数组的长度相等。鱼的行为符合以下几个条件:
  所有的鱼都同时开始游动，每次按照鱼的方向，都游动一个单位距离；
  当方向相对时，大鱼会吃掉小鱼；
  鱼的大小都不一样。
  输入：Size = [4, 2, 5, 3, 1], Dir = [1, 1, 0, 0, 0]
  输出：3
  完成solution(Size, Dir)来计算还剩下几条鱼？

---

单调栈

• 定义：单调栈就是指栈中的元素必须是按照升序排列的栈，或者是降序排列的栈。
  升序排列的栈称为递增栈
  降序排列的栈称为递减栈
  特点：任何时候都需要保证栈的有序性

---

• 例题1：一个整数数组 A，找到每个元素：右边第一个比我小的下标位置，没有则用 -1 表示。（找出数组中右边比我小的元素）
  输入：[5, 2]
  输出：[1, -1]
  解释：因为元素 5 的右边离我最近且比我小的位置应该是 A[1]，最后一个元素 2 右边没有比 2 小的元素，所以应该输出 -1。

类似题：
数组中右边第一个比我大的元素的位置
数组中元素左边离我最近且比我小的元素的位置
数组中元素左边离我最近且比我大的元素的位置

• 例题2：给定一个正整数数组和 k，要求依次取出 k 个数，输出其中数组的一个子序列，需要满足：1. 长度为 k；2.字典序最小。
  输入：nums = [3,5,2,6], k = 2
  输出：[2,6]
  解释：在所有可能的解：{[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 字典序最小。

解题思路