LeetCode Tag Validator Given a string representing a code snippet, you need to implement a tag validator to parse the code and return whether it is valid. A code snippet is valid if all the following rules hold:

1. The code must be wrapped in a valid closed tag. Otherwise, the code is invalid.
2. A closed tag (not necessarily valid) has exactly the following format : <TAG_NAME>TAG_CONTENT</TAG_NAME>. Among them, <TAG_NAME> is the start tag, and </TAG_NAME> is the end tag. The TAG_NAME in start and end tags should be the same. A closed tag is valid if and only if the TAG_NAME and TAG_CONTENT are valid.
3. A valid TAG_NAME only contain upper-case letters, and has length in range [1,9]. Otherwise, the TAG_NAME is invalid.
4. A valid TAG_CONTENT may contain other valid closed tags, cdata and any characters (see note1) EXCEPT unmatched <, unmatched start and end tag, and unmatched or closed tags with invalid TAG_NAME. Otherwise, the TAG_CONTENT is invalid.
5. A start tag is unmatched if no end tag exists with the same TAG_NAME, and vice versa. However, you also need to consider the issue of unbalanced when tags are nested.
6. A < is unmatched if you cannot find a subsequent >. And when you find a < or </, all the subsequent characters until the next > should be parsed as TAG_NAME (not necessarily valid).
7. The cdata has the following format : <![CDATA[CDATA_CONTENT]]>. The range of CDATA_CONTENT is defined as the characters between <![CDATA[ and the first subsequent]]>.
8. CDATA_CONTENT may contain any characters. The function of cdata is to forbid the validator to parse CDATA_CONTENT, so even it has some characters that can be parsed as tag (no matter valid or invalid), you should treat it as regular characters.

Valid Code Examples:

Input: "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: True
Explanation:
The code is wrapped in a closed tag : <DIV> and </DIV>.
The TAG_NAME is valid, the TAG_CONTENT consists of some characters and cdata.
Although CDATA_CONTENT has unmatched start tag with invalid TAG_NAME, it should be considered as plain text, not parsed as tag.
So TAG_CONTENT is valid, and then the code is valid. Thus return true.
Input: "<DIV>>>  ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>"
Output: True
Explanation:
We first separate the code into : start_tag|tag_content|end_tag.
start_tag -> "<DIV>"
end_tag -> "</DIV>"
tag_content could also be separated into : text1|cdata|text2.
text1 -> ">>  ![cdata[]] "
cdata -> "<![CDATA[<div>]>]]>", where the CDATA_CONTENT is "<div>]>"
text2 -> "]]>>]"
The reason why start_tag is NOT "<DIV>>>" is because of the rule 6.
The reason why cdata is NOT "<![CDATA[<div>]>]]>]]>" is because of the rule 7.

Invalid Code Examples:

Input: "<A>  <B> </A>   </B>"
Output: False
Explanation: Unbalanced. If "<A>" is closed, then "<B>" must be unmatched, and vice versa.
Input: "<DIV>  div tag is not closed  <DIV>"
Output: False
Input: "<DIV>  unmatched <  </DIV>"
Output: False
Input: "<DIV> closed tags with invalid tag name  <b>123</b> </DIV>"
Output: False
Input: "<DIV> unmatched tags with invalid tag name  </1234567890> and <CDATA[[]]>  </DIV>"
Output: False
Input: "<DIV>  unmatched start tag <B>  and unmatched end tag </C>  </DIV>"
Output: False

Note:

1. For simplicity, you could assume the input code (including the any characters mentioned above) only contain letters, digits, '<','>','/','!','[',']' and ' '.

---

本题需要写一个检查简单html源代码标签是否匹配的程序。规则有很多，8条，比如tag长度必须在[1,9]，且必须是大写字母，还有<![CDATA[CDATA_CONTENT]]>这个东西，经常会在html源代码中看见。 这题在比赛的时候没想清楚，思路比较乱。比赛结束之后，看了讨论区的解答，感觉思路好清晰，借鉴过来。 需要检查的主要有两个部分，一是Tag标签匹配，二是cdata。对于cdata，只要找到，则可以过滤掉<![CDATA[和]]>之间的所有内容。对于Tag标签匹配，类似括号匹配，可以用栈来实现。 但是因为Tag和cdata的开头都有<，我们匹配的时候， 应该从特殊到一般，即首先考虑是<![CDATA，其次考虑是</，然后考虑是<，最后就是一般性的字符了。 当遇到<![CDATA时，找到对应的]]>，下标快速跳到]]>的下一位。 当遇到</时，说明遇到了一个结束Tag，此时判断Tag是否合法，如果合法，从栈中弹出开始Tag，判断开始Tag和结束Tag是否匹配。 当遇到<时，说明遇到了一个开始Tag，判断Tag是否合法，如果合法，则压栈。 如果是一般性的字符，下标直接向前进。 需要注意的是，如果i!=0但是栈为空，说明当前的字符不在某个Tag标签内，比如这个样例：<![CDATA[wahaha]]]><![CDATA[]> wahaha]]>，一上来就是cdata，这是不合法的，因为所有内容都应该在标签对内。 完整代码如下： [cpp] class Solution { private: bool checkTag(const string &tag) { if (tag.size() < 1 || tag.size() > 9)return false; for (const auto &c : tag) { if (!isupper(c))return false; } return true; } public: bool isValid(string code) { stack<string> stk; int i = 0; while (i < code.size()) { if (i > 0 && stk.empty())return false; if (code.substr(i, 9) == "<![CDATA[") { int end = code.find("]]>", i); if (end == string::npos)return false; i = end + 3; } else if (code.substr(i, 2) == "</") { int end = code.find(‘>’, i); if (end == string::npos)return false; string tag = code.substr(i + 2, end – i – 2); if (!checkTag(tag))return false; if (stk.empty() || stk.top() != tag)return false; else stk.pop(); i = end + 1; } else if (code[i] == ‘<‘) { int end = code.find(‘>’, i); if (end == string::npos)return false; string tag = code.substr(i + 1, end – i – 1); if (!checkTag(tag))return false; stk.push(tag); i = end + 1; } else { ++i; } } return stk.empty(); } }; [/cpp] 本代码提交AC，用时12MS。]]>

378. Kth Smallest Element in a Sorted Matrix 378. Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n². 378. Kth Smallest Element in a Sorted Matrix

---

给定一个矩阵，该矩阵每行和每列都是有序的，要找出第k小的数。 如果只利用每行或者每列是有序的，则可以使用堆解决。我们以行为例，那么每行都是有序的，则相当于把所有行进行n路归并，然后找到第k小的数。所以我们构建一个最小堆，首先把所有行的首元素放到堆中，然后n路归并k次，每次弹出堆顶元素（即当前最小值），然后把原堆顶元素所在行的下一个元素放入堆中。k次归并结束之后，堆顶元素即为第k小的元素。 代码如下：

class Solution {
private:
    struct Node {
        int val, row, col;
        Node(int v = 0, int r = 0, int c = 0)
            : val(v)
            , row(r)
            , col(c){};
        friend bool operator<(const Node& n1, const Node& n2) { return n1.val > n2.val; }
    };
public:
    int kthSmallest(vector<vector<int> >& matrix, int k)
    {
        int n = matrix.size();
        priority_queue<Node> pn;
        for (int i = 0; i < n; ++i)
            pn.push(Node(matrix[i][0], i, 0));
        Node t;
        while (k–) {
            t = pn.top();
            pn.pop();
            if (t.col < n – 1)
                pn.push(Node(matrix[t.row][t.col + 1], t.row, t.col + 1));
        }
        return t.val;
    }
};

本代码提交AC，用时45MS。时间复杂度是O(klgn)，堆的大小为n，每次归并调整堆需要lgn时间，一共需要归并k次，所以总的时间复杂度是O(klgn)。
另外用二分的方法可以同时利用行有序和列有序的特点。这种矩阵可以看成一个曲面，曲面的最低点为左上角元素left，最高点为右下角元素right，所以曲面就是从左上角向上延伸到右下角（想象一下MATLAB画的图）。那么第k小的数肯定在[left,right]范围内，我们可以二分查找这个区间。假设中点是mid，则我们在每一行找找比mid小的数有多少个，加起来如果等于cnt，则说明mid这个数排在第cnt位。因为每一行也是有序的，所以可以直接用upper_bound查找第一个比mid大的数。
代码如下：

class Solution {
public:
    int kthSmallest(vector<vector<int> >& matrix, int k)
    {
        int n = matrix.size(), left = matrix[0][0], right = matrix[n – 1][n – 1];
        while (left <= right) {
            int mid = left + (right – left) / 2;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) – matrix[i].begin();
            }
            if (cnt < k)
                left = mid + 1;
            else
                right = mid – 1;
        }
        return left;
    }
};

本代码提交AC，用时43MS。时间复杂度是O(lgX nlgn)，X为[left,right]的区间大小，ngln是对于每个mid，都需要在每一行二分查找比mid小的数的个数。
还可以将上述复杂度降为O(lgX n)。就是在找cnt，不需要每一行都二分查找，我们可以从矩阵的左下角往右上角阶梯查找，如果要查找的数更大，则往右移，否则往上移，每次查询只需要O(n)的时间，所以总时间是O(lgX n)。
代码如下：

class Solution {
private:
    int count_less_equal(vector<vector<int> >& matrix, int num)
    {
        int n = matrix.size(), i = n – 1, j = 0, cnt = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= num) {
                cnt += i + 1;
                ++j;
            }
            else
                –i;
        }
        return cnt;
    }
public:
    int kthSmallest(vector<vector<int> >& matrix, int k)
    {
        int n = matrix.size(), left = matrix[0][0], right = matrix[n – 1][n – 1];
        while (left <= right) {
            int mid = left + (right – left) / 2;
            int cnt = count_less_equal(matrix, mid);
            if (cnt < k)
                left = mid + 1;
            else
                right = mid – 1;
        }
        return left;
    }
};

本代码提交AC，用时39MS。

LeetCode Verify Preorder Serialization of a Binary Tree One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node. Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree. Each comma separated value in the string must be either an integer or a character '#' representing null pointer. You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3". Example 1: "9,3,4,#,#,1,#,#,2,#,6,#,#" Return true Example 2: "1,#" Return false Example 3: "9,#,#,1" Return false

---

根据树的先序遍历结果，在不重构树的情况下，判断该先序遍历是否合法。 解法1，使用栈。因为先序遍历的顺序是根左右，如果我们遇到序列x,#,#，其中x不是#时，说明x的左右孩子都是#，此时，我们将x,#,#替换为#，表示将以x为根的子树替换为一个#。如此循环，如果栈中最终只剩下一个#，说明该序列合法。 比如样例”9,3,4,#,#,1,#,#,2,#,6,#,#”：

• 9,3,4,#,# → 9,3,#
• 9,3,#,1,#,# → 9,3,#,# → 9,#
• 9,#,2,#,6,#,# → 9,#,2,#,# → 9,#,# → #

不需要担心遇到x,#,#,#的情况，因为在遍历到第二个#时，就符合x,#,#的pattern了，会把x,#,#变成#。 代码如下： [cpp] class Solution { public: bool isValidSerialization(string preorder) { stack<string> stk; int i = 0, j = 0, n = preorder.size(); while (j < n) { while (j < n&&preorder[j] != ‘,’)++j; string node = preorder.substr(i, j – i); if (node == "#") { while (!stk.empty() && stk.top() == "#") { stk.pop(); if (stk.empty())return false; stk.pop(); } } stk.push(node); i = ++j; } return stk.size() == 1 && stk.top() == "#"; } }; [/cpp] 本代码提交AC，用时6MS。 解法2，利用度的信息。一棵二叉树通过题目中的加#策略之后，变成了一棵满二叉树。这里的满是指一个节点要么有两个孩子，要么没有孩子，不存在有一个孩子的情况。（把#也看成孩子） 那么如果是叶子节点，则只贡献一个入度；如果是非叶子节点，则贡献一个入度和两个出度。所以diff=outdegree-indegree不可能是负数。 所以当来了一个节点，先–diff，因为这个节点肯定会贡献一个入度。然后判断这个节点如果是非叶子节点，则diff+=2，因为非叶子节点贡献两个出度。程序结束时，如果diff==0，则说明序列合法，否则不合法。因为就完整的树来说，入度肯定等于出度的，一条边对于父亲节点来说贡献出度，但对于孩子节点来说，贡献入度，所以总的入度和出度是相等的。 初始时，因为根节点没有入度，但是在外层while循环中，我们把根节点也看成普通的节点了。普通节点假设是有入度的，所以一进来就会–diff。所以初始时给根节点也补上一个入度，即diff=1，这样进入while之后，–diff不至于小于0。 代码如下： [cpp] class Solution { public: bool isValidSerialization(string preorder) { int i = 0, j = 0, n = preorder.size(), diff = 1; while (j < n) { while (j < n&&preorder[j] != ‘,’)++j; string node = preorder.substr(i, j – i); if (–diff < 0)return false; if (node != "#")diff += 2; i = ++j; } return diff == 0; } }; [/cpp] 本代码提交AC，用时3MS。 解法3，也是利用度的信息。前面说了，通过题目中的策略，一棵普通二叉树已经变成了一棵满二叉树，满二叉树的特点是叶子节点的数目=非叶子节点的数目+1。简单证明如下： 假设叶子节点数为leaves，非叶子节点数为nonleaves。则总节点数为leaves+nonleaves，总边数就是leaves+nonleaves-1。一条边贡献两个度，所以总度数就是2(leaves+nonleaves-1)。从另一个角度，一个叶子节点贡献一个度，一个非叶子节点贡献3个度，根节点也是非叶子节点，但它只贡献两个读，所以总度数加起来就是leaves+3*nonleaves-1。令2(leaves+nonleaves-1)=leaves+3*nonleaves-1，就解出了leaves=nonleaves+1。 因为先序遍历是根左右，所以我们找一个满足leaves=nonleaves+1的最短前缀，如果这确实是一个合法的序列，则这个最短前缀就应该是序列本身。因为一棵满二叉树，在遍历的过程中是不会满足leaves=nonleaves+1的，只有当整棵树都遍历完之后才会满足这个条件。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

上面这棵树，虽然在遍历到节点2时，如果不再往下遍历了，看起来也是满二叉树，但是2是有孩子的，所以会被判断为nonleaves，所以还是不满足leaves=nonleaves+1。 代码如下： [cpp] class Solution3 { public: bool isValidSerialization(string preorder) { int leaves = 0, nonleaves = 0; int i = 0, j = 0, n = preorder.size(); while (j < n) { while (j < n&&preorder[j] != ‘,’)++j; string node = preorder.substr(i, j – i); if (node == "#")++leaves; else ++nonleaves; i = ++j; if (leaves – nonleaves == 1 && j < n)return false; } return leaves – nonleaves == 1; } }; [/cpp] 本代码提交AC，用时6MS。]]>

LeetCode 132 Pattern Given a sequence of n integers a₁, a₂, …, a_n, a 132 pattern is a subsequence a_i, a_j, a_k such that i < j < k and a_i < a_k < a_j. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list. Note: n will be less than 15,000. Example 1:

Input: [1, 2, 3, 4]
Output: False
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: [3, 1, 4, 2]
Output: True
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: [-1, 3, 2, 0]
Output: True
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

---

给定一个数组，问数组中是否存在132这样的子序列。132是指i<j<k，但a[i]<a[k]<a[j]的形式，132就是这样一个例子，中间最大，右边次之，左边最小。 解法1。朴素解法，直接查找是否存在这样的i,j,k。首先找i，即满足a[i]<a[i+1]这样的i。然后找j，我们希望a[j]越大越好，这样的话，才可能找到a[k]<a[j]的k，所以a[j]<a[j+1]时，j++，因为前面有更大的a[j]，照样满足a[i]<a[j]，还可能更容易找到小于a[j]的a[k]。当确定i,j之后，a[k]就在j后面不断找在a[i]和a[j]之间的数。 代码如下： [cpp] class Solution { public: bool find132pattern(vector<int>& nums) { int i = 0, j = 0, k = 0, n = nums.size(); while (i < n) { while (i < n – 1 && nums[i] >= nums[i + 1])++i; j = i + 1; while (j < n – 1 && nums[j] <= nums[j + 1])++j; k = j + 1; while (k < n) { if (nums[k] > nums[i] && nums[k] < nums[j])return true; ++k; } ++i; } return false; } }; [/cpp] 本代码提交AC，用时299MS。 解法2。使用栈。从数组末尾往前找，我们希望a[j]越大越好，而a[k]最好是次大的，这样a[i]就更容易小于a[k]了。定义一个变量third表示132模式中的第三个数，就是132中的2。初始时令third=INT_MIN。定义一个堆栈stk保存比third大的所有数，如果nums[i]小于third，表示找到了第一个数1，返回true。如果nums[i]大于stk栈顶，表示找到了更大的数，则把stk中的数给third，表示third保存的是次大的数，然后把nums[i]压入stk。 代码如下： [cpp] class Solution { public: bool find132pattern(vector<int>& nums) { stack<int> stk; int third = INT_MIN; for (int i = nums.size() – 1; i >= 0; –i) { if (nums[i] < third)return true; else { while (!stk.empty() && nums[i] > stk.top()) { third = stk.top(); stk.pop(); } stk.push(nums[i]); } } return false; } }; [/cpp] 本代码提交AC，用时23MS，快了不少。]]>

503. Next Greater Element II 503. Next Greater Element II

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number.

Example 1:

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number; 
The second 1's next greater number needs to search circularly, which is also 2.

Note: The length of given array won’t exceed 10000. 503. Next Greater Element II

---

是LeetCode Next Greater Element I的扩展，本题的数组可能包含重复元素，且是循环数组，即往右找到尾之后，可以接着从头开始找更大的数。 同样使用栈，只不过需要扫描两遍数组，且栈中保存的是元素下标，理解之后发现挺巧妙的。 比如nums = [9, 8, 7, 3, 2, 1, 6]，第一遍循环之后，堆栈中从低到顶剩余的元素是9,8,7,6，此时再从头开始扫描一遍数组，9，发现栈顶是6，所以6的右边更大数是9，弹出6；栈顶是7，7的右边更大数也是9；同理8，弹栈；最后栈顶只剩9了。
代码如下：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> ans(n, -1);
        stack<int> idx;
        for (int i = 0; i < 2 * n; ++i) {
            while (!idx.empty() && nums[idx.top()] < nums[i % n]) {
                ans[idx.top()] = nums[i % n];
                idx.pop();
            }
            idx.push(i % n);
        }
        return ans;
    }
};

本代码提交AC，用时119MS。

225. Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• empty() — Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

• You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack). 225. Implement Stack using Queues

---

和LeetCode Implement Queue using Stacks正好相反，本题要用队列实现堆栈的效果。 队列是先进先出的，而堆栈是后进先出。如果用队列q保存数据，则要实现堆栈的pop效果时，需要获取到q的队尾元素，可以不断把q的数据从队首弹出，同时压回队尾，重复n-1次，此时队首元素就是原来的队尾元素了。堆栈的top效果和push的实现方法是类似的。 这种题目就是数据不断的倒腾。。。 完整代码如下：

class MyStack {
private:
    queue<int> m_q;
public: /** Initialize your data structure here. */
    MyStack() {} /** Push element x onto stack. */
    void push(int x) { m_q.push(x); } /** Removes the element on top of the stack and returns that element. */
    int pop()
    {
        int sz = m_q.size();
        for (int i = 0; i < sz – 1; ++i) {
            m_q.push(m_q.front());
            m_q.pop();
        }
        int front = m_q.front();
        m_q.pop();
        return front;
    } /** Get the top element. */
    int top()
    {
        int sz = m_q.size(), front = m_q.front();
        for (int i = 0; i < sz; ++i) {
            front = m_q.front();
            m_q.push(front);
            m_q.pop();
        }
        return front;
    } /** Returns whether the stack is empty. */
    bool empty() { return m_q.empty(); }
};

本代码提交AC，用时3MS。

二刷。用两个queue来模拟stack，不如上面的解法好看：

class MyStack {
private:
	vector<queue<int>> vq_;
	int data_queue_id_;
public:
	/** Initialize your data structure here. */
	MyStack() {
		vq_.push_back(queue<int>());
		vq_.push_back(queue<int>());
		data_queue_id_ = 0;
	}

	/** Push element x onto stack. */
	void push(int x) {
		vq_[data_queue_id_].push(x);
	}

	/** Removes the element on top of the stack and returns that element. */
	int pop() {
		int another_id = 1 - data_queue_id_;
		int last_data = 0;
		while (!vq_[data_queue_id_].empty()) {
			last_data = vq_[data_queue_id_].front();
			vq_[data_queue_id_].pop();
			if (!vq_[data_queue_id_].empty()) {
				vq_[another_id].push(last_data);
			}
		}
		swap(another_id, data_queue_id_);
		return last_data;
	}

	/** Get the top element. */
	int top() {
		int another_id = 1 - data_queue_id_;
		int last_data = 0;
		while (!vq_[data_queue_id_].empty()) {
			last_data = vq_[data_queue_id_].front();
			vq_[data_queue_id_].pop();
			vq_[another_id].push(last_data);
		}
		swap(another_id, data_queue_id_);
		return last_data;
	}

	/** Returns whether the stack is empty. */
	bool empty() {
		return vq_[data_queue_id_].empty();
	}
};

本代码提交AC，用时0MS。

232. Implement Queue using Stacks 232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

• You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue). 232. Implement Queue using Stacks

---

本题要求用堆栈来实现队列的功能。因为堆栈是后进先出，而队列是先进先出，顺序正好相反。比如进入队列的顺序是1,2,3，但是进到堆栈stk1之后，从栈顶到栈底的顺序就变成了3,2,1，此时如果要实现队列出队的效果，就必须借助另一个堆栈stk2，把stk1的内容压入到stk2，这样从栈顶到栈底的顺序就和队列一样了，是1,2,3。 所以本题借助两个堆栈stk1和stk2，stk1就是常规的数据来了就压栈，当需要实现队列的pop效果时，就借助stk2倒腾一下，如果又要实现队列的push效果时，又要把stk2的数据捣腾回stk1。 总的来说，我们使用懒人规则，每次直到调用某个操作，且当前stk*不能满足要求时，才捣腾stk1和stk2。 完整代码如下：

class MyQueue {
private:
    stack<int> stk1, stk2; // 输入来源1,2,3，stk1从栈底到栈顶的顺序是1,2,3，stk2从栈底到栈顶的顺序是3,2,1
public: /** Initialize your data structure here. */
    MyQueue() {} /** Push element x to the back of queue. */
    void push(int x)
    {
        while (!stk2.empty()) {
            stk1.push(stk2.top());
            stk2.pop();
        }
        stk1.push(x);
    } /** Removes the element from in front of queue and returns that element. */
    int pop()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        int top = stk2.top();
        stk2.pop();
        return top;
    } /** Get the front element. */
    int peek()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        return stk2.top();
    } /** Returns whether the queue is empty. */
    bool empty() { return stk1.empty() && stk2.empty(); }
};

本代码提交AC，用时3MS。
二刷。其实push的时候可以不需要把stk2的数据倒腾回stk1，stk2的数据始终是队列头的，stk1的数据始终是队列尾的，代码如下：

class MyQueue {
private:
    stack<int> stk1, stk2;
    void adjust()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
    }
public: /** Initialize your data structure here. */
    MyQueue() {} /** Push element x to the back of queue. */
    void push(int x) { stk1.push(x); } /** Removes the element from in front of queue and returns that element. */
    int pop()
    {
        if (stk2.empty())
            adjust();
        int ans = stk2.top();
        stk2.pop();
        return ans;
    } /** Get the front element. */
    int peek()
    {
        if (stk2.empty())
            adjust();
        int ans = stk2.top();
        return ans;
    } /** Returns whether the queue is empty. */
    bool empty() { return stk1.empty() && stk2.empty(); }
};

本代码提交AC，用时3MS。

215. Kth Largest Element in an Array215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.215. Kth Largest Element in an Array

---

本题要求一个未排序数组中第k大的数。
解法1，直接从大到小排序，然后取第k个数，时间复杂度O(nlgn)。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        sort(nums.begin(), nums.end(), std::greater<int>());
        return nums[k – 1];
    }
};

本代码提交AC，用时16MS。
解法2，借助快排的思路，每次选择一个枢纽pivot，把区间[left,right]划分为比pivot大和小的两个部分，然后就能确定pivot的最终位置，如果其下标正好是k-1，则说明pivot就是第k大的数。否则可以判断第k大的数在左半边还是右半边，然后递归在其中一半查找第k大的数。时间复杂度可以由T(n)=T(n/2)+O(n)解出是O(n)，注意我们只需要在其中一半递归，所以是加一个T(n/2)。
代码如下：

class Solution {
private:
    int helper(vector<int>& nums, int left, int right, int k)
    {
        if (left == right)
            return nums[left];
        int pivot = nums[left];
        int l = left, r = right;
        while (l < r) {
            while (l < r && nums[r] <= pivot)
                –r;
            if (l >= r)
                break;
            nums[l] = nums[r];
            while (l < r && nums[l] >= pivot)
                ++l;
            if (l >= r)
                break;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        if (l + 1 == k)
            return pivot;
        if (k < l + 1)
            return helper(nums, left, l – 1, k);
        else
            return helper(nums, l + 1, right, k);
    }
public:
    int findKthLargest(vector<int>& nums, int k) { return helper(nums, 0, nums.size() – 1, k); }
};

本代码提交AC，用时39MS，居然比直接排序还慢。。。
解法3，使用堆排序。对原数组建一个最大堆，然后不断的把前k-1个堆顶弹出，下一个堆顶元素就是第k大的元素。建堆时间为O(n)，维护堆的性质需要O(lgn)时间，所以总时间复杂度为O(klgn+n)。
代码如下：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        priority_queue<int> pq(nums.begin(), nums.end());
        for (int i = 0; i < k – 1; ++i)
            pq.pop();
        return pq.top();
    }
};

本代码提交AC，用时9MS，是最快的。
二刷。还是使用快排划分的方法，但是这次把partition的过程单独抽出来了，逻辑更清晰，代码如下：

class Solution {
private:
    int partition(vector<int>& nums, int start, int end)
    {
        if (start >= end)
            return start;
        int i = start, j = end, pivot = nums[start];
        while (i < j) {
            while (i < j && nums[j] <= pivot)
                –j; // 注意符号，从大到小排序
            if (i < j) {
                nums[i] = nums[j];
                ++i;
            }
            while (i < j && nums[i] > pivot)
                ++i; // 注意符号，从大到小排序
            if (i < j) {
                nums[j] = nums[i];
                –j;
            }
        }
        nums[i] = pivot;
        return i;
    }
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        int start = 0, end = nums.size() – 1;
        while (true) {
            int p = partition(nums, start, end);
            if (p + 1 == k)
                return nums[p];
            else if (p + 1 < k)
                start = p + 1;
            else
                end = p – 1;
        }
        return -1;
    }
};

本代码提交AC，用时23MS。

三刷。更简洁不易出错的快排划分方法：

class Solution {
private:
	int FindK(vector<int>& nums, int left, int right, int k) {
		int pivot = nums[right];
		int next_idx = left;
		for (int i = left; i <= right; ++i) {
			if (nums[i] > pivot) {
				swap(nums[i], nums[next_idx++]);
			}
		}
		swap(nums[right], nums[next_idx]);
		int rank = next_idx + 1 - left;
		if (rank == k)return pivot;
		else if (k < rank)return FindK(nums, left, next_idx - 1, k);
		else return FindK(nums, next_idx + 1, right, k - rank);
	}
public:
	int findKthLargest(vector<int>& nums, int k) {
		return FindK(nums, 0, nums.size() - 1, k);
	}
};

本代码提交AC，用时212MS。

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• getMin() — Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

---

本题要实现一个最小栈，使得push, pop, top以及getMin都是以O(1)的时间完成。

这是一个非常经典的双栈法题目，我居然不知道。同时使用两个栈，一个普通的用于存放所有数据allStack，另一个只用于存储最小值序列minStack。 push的时候，每次都把x push进allStack。如果minStack为空，则是第一次push，要把x push进minStack；如果minStack非空，则当x小于等于minStack栈顶时，可以把x push进minStack。注意当x等于minStack栈顶的时候也是需要进栈的，因为有可能有重复元素，比如对0,1,0依次进栈，遇到后面的0时，minStack只有前一个0，此时如果后一个0不进栈，如果下一步是pop的话，就会把minStack中的上一个0 pop掉，那么此时getMin时就会出错，因为此时minStack里没东西了，但allStack还保留着0和1，正确的最小值应该是前一个0。 pop时，allStack正常pop。如果pop出来的值等于minStack的栈顶，则minStack也需要pop。 top就取allStack的top。 getMin就取minStack的top。 完整代码如下：

class MinStack {
private:
    stack<int> allStack, minStack;

public: /** initialize your data structure here. */
    MinStack() {}
    void push(int x)
    {
        if (minStack.empty()) {
            minStack.push(x);
        }
        else if (x <= minStack.top()) { // 注意是<=而不是<
            minStack.push(x);
        }
        allStack.push(x);
    }
    void pop()
    {
        int top = allStack.top();
        allStack.pop();
        if (top == minStack.top()) {
            minStack.pop();
        }
    }
    int top() { return allStack.top(); }
    int getMin() { return minStack.top(); }
};

本代码提交AC，用时29MS。

二刷。其实可以更简单一点，辅助的minStack大小始终和allStack一样，当新入元素小于minStack栈顶元素时，自然入minStack；否则，就把minStack栈顶的元素再入一次栈。这样就使得两个栈的大小一样，pop的时候可以同时pop，减少了各种if判断。
完整代码如下：

class MinStack {
private:
    stack<int> allStack, minStack;
public: /** initialize your data structure here. */
    MinStack() {}
    void push(int x)
    {
        if (minStack.empty() || x < minStack.top()) {
            minStack.push(x);
        }
        else {
            minStack.push(minStack.top());
        }
        allStack.push(x);
    }
    void pop()
    {
        allStack.pop();
        minStack.pop();
    }
    int top() { return allStack.top(); }
    int getMin() { return minStack.top(); }
};

本代码提交AC，用时29MS。