一.方法介绍

  1. 对于重写栈使其能在O(1)内返回最小值的，通过定义一个辅助栈，这个栈保存主栈中的每个元素所对应的最小值，在每次入栈的时候，比较一下就行

二.leetcode题目

48.旋转图像-(思路清晰)

题目链接
每次只考虑四个间隔90度的旋转，matrix[i][j]会被旋转到matrix[j][n-i]的位置(n=matrix.size()-1)
i从行从[0, n/2]
j从列从[i, n-i)开始

240.搜索二维矩阵||-(不循规蹈矩)

题目链接
假如从左上开始遍历，当当前值比目标值小，有两种遍历方向，一种是往右，另一种是往下，不好选择
因此，可以采用从右上开始遍历，若当前值比目标值大，则只能往左走，若当前值比目标值小，则只能往下走。很合理！

448.找到数组中消失的数字-(巧用下标)

题目链接
可以建立n个桶，把所有重新出现的位置进行标记，然后再遍历一遍数组，即可找到没有出现过的数字。

不额外申请空间：
不过有一点需要注意，由于是n个数，正好要确认的数的范围是1~n，因此可以用下标来表示1~n，用nums[i]的正负来标记i+1是否在数组中，原来是正的，如果出现i+1，则将nums[i]变成负的。最后遍历一遍nums数组找到仍然是正的值，其下标+1即为未出现的数字。

769.最多能完成排序的块-(分析问题，规律)

题目链接
由于是把0~n填入数组，因此最后排好序的数组的值和下标一定是相等的。从这一点出发，对于原数组，用max记录遍历到下标 i 的当前的最大值，假如这个值等于数组下标，说明这个最大值是要被填到这个位置的，则说明前面的位置都是可以通过排序正好填上的(假如填不上，则最大值一定是不等于遍历到的当前的下标的，显然矛盾)。于是这一段便可以分开作为一个块，于是只要统计有多少个这样的情况出现即可。

232.用栈实现队列

题目链接
用栈的操作来实现一个队列。
这里采用两个栈，in, out
in负责队列的尾部进数，out则负责队列的头部出数
对于头部出数，假如out为空，则通过自定义函数inToout()将in逆转一下放进out里，
image.png

225.用队列实现栈

题目链接

  1. 采用两个队列，在push时，就用两个队列先实现逆序，把顺序倒好，比如一开始两个队列为空，push(2)时，是(->2-> ， ->->)，再push(3)时，则是(->->, ->2-3->)，依次类推

    155.最小栈-(存储最小值的栈-顺序)

    题目链接
    方式一： vector方式实现栈
    vector自带栈的一些基本操作，比如压栈, 弹栈, 访问栈顶,
    之所以使用vector，可以对其进行遍历操作。
    对于在常数时间内检索到最小元素的方式
    可以用一个变量存储当前栈的最小值minx，在有新元素入栈时，更新minx，在有元素弹栈时，如果弹栈的元素和minx相等，则重新遍历一遍栈，再次得到新的minx.

方式二：双栈
一个栈是原栈，另一个栈用来存储最小值的新栈，
对于新栈，栈顶表示原栈里当前高度下所有值的最小值，每当原栈里插入一个数字时，若该数字小于等于新栈栈顶，则表示这个数字在原栈里是最小值，我们将其同时插入新栈内。否则，将最小值栈顶元素再push一遍。

739.每日温度-(单调栈的使用)

题目链接
二重循环的简单暴力的方法会超时，因此要另寻出路。

如何放在一起进行批处理？栈?
这里维护一个以温度从栈底到栈顶单调递减栈，对于日期p，若p的温度比栈顶的日期q的温度高，则表示找到q至少要等待的天数，弹出q，继续往下找，直到找到比p的温度高或者栈为空，于是把p打入栈中，相当于又维持着栈的递减性。
这里之所以能节省时间，是因为有些天数的升温天数是可以放在一起处理的，比如 21,20,19,18,23。这里前几天都是直接压栈的，等到23出现，就会把前面的连续弹栈。

在最后，栈里面如果还剩余一些日期，则是表示温度没有比这些高的，将其弹栈，并将等待天数设为0。

678.有效的括号字符串

题目链接

法一：双栈法

  1. 栈left用来存放左括号的下标，栈asterisk用来存放星号的下标。
  2. 在遍历时，当遇到左括号，将其下标压入left中；遇到星号，将其下标压入asterisk中；遇到右括号，优先将left的弹出一个与其匹配，若left栈为空，则将asterisk中弹出一个与其匹配（取出一个星号变成左括号）
  3. 遍历完后，若left栈不为空，则需要从asterisk栈中取星号变成右括号继续匹配，不过有个原则是，要匹配的星号的下标必须比要匹配的左括号的下标要大。如果不大，则说明匹配不成功，字符串无效。

  4. 最后只有当栈left为空时，字符串才是有效的

    1. bool checkValidString(string s) {
    2.      stack<int> left, asterisk;
    3.      int i,j;
    4.      for (i=0;i<s.size();i++) {
    5.          if (s[i]=='('){
    6.              left.push(i);
    7.          }else if (s[i]=='*')
    8.              asterisk.push(i);
    9.          else {
    10.              if (left.empty()&&asterisk.empty())
    11.                  return false;
    12.              if (!left.empty())
    13.                  left.pop();
    14.              else 
    15.                  asterisk.pop();
    16.          }
    17.      }
    18.      while (!left.empty()&&!asterisk.empty()) {
    19.          if (left.top()>asterisk.top())
    20.              return false;
    21.          left.pop();
    22.          asterisk.pop();
    23.      }
    24.      return left.empty();
    25.  }

    法二：贪心法

  5. 由于星号既可以变成左括号，又可以变成右括号，又可以对字符串匹配不影响，而且，未匹配的左括号的数目是影响最终是否匹配成功的关键。因此，遍历过程中，维护未匹配的左括号的最小值mincount和最大值maxcount。

  6. 几点需要注意：mincount是将遇到的星号都视为右括号得到的，其在变化过程中，是从[0,….)开始，不能小于0，因为小于0的话，就会出现右括号在左括号之前的情况，因此在mincount=max(mincount变化,0)；maxcount是将遇到的星号都视为左括号得到的，当maxcount小于0时，说明已经没有足够的左括号来匹配右括号，此时是无效的字符串。
  7. 遍历时，当遇到左括号，则mincount和maxcount都加1，
    当遇到右括号，则maxcount减1，mincount=max(mincount-1,0)。此时判断maxcount。
    当遇到星号，则maxcount加1，mincount=max(mincount-1,0)。
    1. bool checkValidString(string s) {
    2.      int mincount=0,maxcount=0;
    3.      for (char ch:s){
    4.          if (ch=='('){
    5.              ++mincount;
    6.              ++maxcount;
    7.          }else if (ch=='*'){
    8.              mincount=(mincount)? mincount-1: 0;
    9.              ++maxcount;
    10.          }else {
    11.              mincount=(mincount)? mincount-1: 0;
    12.              --maxcount;
    13.               if (maxcount<0)
    14.                  return false;
    15.          }
    16.      }
    17.      return mincount==0;
    18. }