训练题：滑动窗口最大值

题目：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

思路：k个数里的最大值，首先想到堆，不过搞半天没出路，转移到考虑队列的数据结构。
max队列，快速获取当前队列的最大值。

  • 时间复杂度：O（n）
  • 空间复杂度：考虑返回值：O（n）；不考虑返回值O（k）。
  3. class MaxQueue {
  4. public:
  5.     MaxQueue() {
  7.     }
  9.     int max_value() {
  10.         if(maxQueue.empty()) return -1;
  11.         return maxQueue.front();
  12.     }
  14.     void push(int value) {
  15.         dataQueue.push(value);
  16.         for(; !maxQueue.empty() && maxQueue.back() < value; maxQueue.pop_back());
  17.         maxQueue.push_back(value);
  18.     }
  20.     int pop() {
  21.         if(dataQueue.empty()) return -1;
  23.         int ret = dataQueue.front();
  24.         dataQueue.pop();
  25.         if(maxQueue.front() == ret) maxQueue.pop_front();
  26.         return ret;
  27.     }
  28. private:
  29.     queue<int> dataQueue;
  30.     deque<int> maxQueue;
  31. };
  33. class Solution {
  34. public:
  35.     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  37.         if(k > nums.size() || nums.empty()) return {};
  39.         const auto size = nums.size();
  40.         vector<int> ret;
  42.         MaxQueue q;
  44.         int idx;
  45.         for(idx = 0; idx < k; ++idx) q.push(nums[idx]);
  46.         ret.push_back(q.max_value());
  48.         for(; idx < size; ++idx){
  49.             q.push(nums[idx]);
  50.             q.pop();
  51.             ret.push_back(q.max_value());
  52.         }
  54.         return ret;
  55.     }
  56. };

训练题：max队列

题目：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

  2. class MaxQueue {
  3. public:
  4.     MaxQueue() {
  6.     }
  8.     int max_value() {
  9.         if(maxQueue.empty()) return -1;
  10.         return maxQueue.front();
  11.     }
  13.     void push_back(int value) {
  14.         dataQueue.push(value);
  15.         for(; !maxQueue.empty() && maxQueue.back() < value; maxQueue.pop_back());
  16.         maxQueue.push_back(value);
  17.     }
  19.     int pop_front() {
  20.         if(dataQueue.empty()) return -1;
  22.         int ret = dataQueue.front();
  23.         dataQueue.pop();
  24.         if(maxQueue.front() == ret) maxQueue.pop_front();
  25.         return ret;
  26.     }
  27. private:
  28.     queue<int> dataQueue;
  29.     deque<int> maxQueue;
  30. };

训练题：min栈

题目：http://t.cn/A6VtAJtX

  1. class MinStack {
  2. public:
  3.     /** initialize your data structure here. */
  4.     MinStack() {
  6.     }
  8.     void push(int x) {
  9.         stk.push(x);
  11.         // 如果minStk栈顶的最小值没比待插入的x更小，那就要更新最小值了。
  12.         if(minStk.empty() || x <= minStk.top()) minStk.push(x);
  13.     }
  15.     void pop() {
  16.         if(stk.empty()) return;
  17.         if(stk.top() == minStk.top()) minStk.pop();
  18.         stk.pop();
  19.     }
  21.     int top() {
  22.         return stk.top();
  23.     }
  25.     int min() {
  26.         return minStk.top();
  27.     }
  28. private:
  29.     stack<int> minStk;
  30.     stack<int> stk;
  31. };

训练题：压栈/弹栈序列

题目：http://t.cn/A6qva3VL

方法一

  2. bool validateStackSequences( vector<int> &pushed, vector<int> &popped )
  3. {
  4.     if( pushed.size() != popped.size() ) { return false; }
  6.     stack<int> stk;
  8.     int popIdx = 0;
  9.     for( const auto &i : pushed )
  10.     {
  11.         stk.push( i );
  12.         while( !stk.empty() && stk.top() == popped[popIdx] )
  13.         {
  14.             stk.pop();
  15.             ++popIdx;
  16.         }
  17.     }
  18.     return stk.empty();
  19. }

方法二：模拟法

  2. bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
  3.     if(pushed.size() != popped.size()) return false;
  5.     const auto size_push = pushed.size();
  6.     const auto size_pop  = popped.size();
  7.     stack<int> s;
  9.     int popIdx = 0;
  10.     for(int pushIdx = 0; popIdx < size_pop;)
  11.     {
  12.         for(; (s.empty() || s.top() != popped[popIdx]) && pushIdx < size_push; ++pushIdx )
  13.             s.push(pushed[pushIdx]);
  15.         if(!s.empty() && s.top() == popped[popIdx]){
  16.             s.pop();
  17.             ++popIdx;
  18.         }
  19.         else if(pushIdx == size_push) return false;
  20.     }
  22.     return popIdx == size_pop;
  23. }

训练题：两个栈实现队列

题目：http://t.cn/A6yvWVAG

  2. class CQueue
  3. {
  4. public:
  5.     CQueue()
  6.     {
  8.     }
  10.     void appendTail( int value )
  11.     {
  12.         stack1.push( value );
  13.     }
  15.     int deleteHead()
  16.     {
  17.         if( stack2.empty() ) for( ; !stack1.empty(); stack1.pop() ) { stack2.push( stack1.top() ); }
  19.         int ret = -1;
  20.         if( !stack2.empty() )
  21.         {
  22.             ret = stack2.top();
  23.             stack2.pop();
  24.         }
  25.         return ret;
  26.     }
  27. private:
  28.     stack<int> stack1;
  29.     stack<int> stack2;
  30. };