剑指offer - 栈与队列 - 《c 知识库》

剑指 Offer 59 - I. 滑动窗口的最大值

总是忘记优先队列！！！！！！

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(k == 0){
            return {};
        }
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k) {//保证区间最大值在滑窗范围内
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

单调队列

使用双端队列deque

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(k == 0) return {};
        int n = nums.size();
        deque<int> q;//双端队列
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {//当数字大于尾部元素时，将尾部元素弹出，
            //这样的话这个队列将会是一个从低到上的递增队列
            //有点像人工优先队列
                q.pop_back();
            }
            q.push_back(i);
        }

        vector<int> ans = {nums[q.front()]};
        for (int i = k; i < n; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() <= i - k) {//当最大值不在滑动窗口的范围中时，弹出最大值
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

剑指 Offer 59 - II. 队列的最大值

核心思想还是维护一个从底到上递增双端队列。同时可以进行前后的插入操作
核心思想在于两个大值之间的小值根本就不会影响到最终结果，因此只需要递增的值就可以了，
这个想法非常重要，和上面一题的单调解法的思路一摸一样

class MaxQueue {
    queue<int> q;
    deque<int> d;//双端队列
public:
    MaxQueue() {
    }

    int max_value() {
        if (d.empty())
            return -1;
        return d.front();
    }

    void push_back(int value) {
        while (!d.empty() && d.back() < value) {//维护一个递增的队列
            d.pop_back();
        }
        d.push_back(value);
        q.push(value);
    }

    int pop_front() {
        if (q.empty())
            return -1;
        int ans = q.front();
        if (ans == d.front()) {
            d.pop_front();
        }
        q.pop();
        return ans;
    }
};

剑指 Offer II 041. 滑动窗口的平均值（easy）

几乎没有难点，主要是可以有优化写法
防止和溢出。 ```cpp class MovingAverage { private: double average = 0; queue q; double size, qsize = 0; public: /* Initialize your data structure here. / MovingAverage(int size):size(size) { }

double next(int val) {
```
  if(qsize == size){
      average = average - q.front()/size + val/size;
      q.pop();
      q.push(val);
  } else {
      average = qsize/(qsize+1)*average + val/(qsize+1);
      q.push(val);
      qsize++;
  }
  return average;
```
} };

<a name="TPaSy"></a>
### [剑指 Offer II 042. 最近请求次数](https://leetcode-cn.com/problems/H8086Q/)（easy）

- 平平无奇
```cpp
class RecentCounter {
    queue<int> q;
public:
    RecentCounter() {

    }

    int ping(int t) {
        while(!q.empty()&&q.front() < (t-3000)){
            q.pop();
        }
        q.push(t);
        return q.size();
    }
};

剑指 Offer II 043. 往完全二叉树添加节点（重点）

需要注意队列先进出的特点
从左到右先进

出的时候是从左到右 ```cpp class CBTInserter { TreeNode root; queue<TreeNode> q; public: CBTInserter(TreeNode* root) {

  this->root = root;
  q.push(root);
  while(!q.empty()){
      TreeNode* node = q.front();
      if(node->left&&node->right){
          q.pop();
          q.push(node->left);
          q.push(node->right);
      } else {
          break;
      }
  }
  if(q.front()->left) q.push(q.front()->left);

}

int insert(int v) {

  int res = q.front()->val;
  if(!q.front()->left){
      q.front()->left = new TreeNode(v);
      q.push(q.front()->left);
  } else if(!q.front()->right){
      q.front()->right = new TreeNode(v);
      q.push(q.front()->right);
      q.pop();
  }
  return res;

}

TreeNode* get_root() {

  return root;

} };

<a name="v5Eeg"></a>
### [剑指 Offer II 044. 二叉树每层的最大值](https://leetcode-cn.com/problems/hPov7L/)

- 和二叉树的层序遍历类似
```cpp
class Solution {
    public:
    vector<int> largestValues(TreeNode* root) {
        if(!root) return {};
        queue<TreeNode*> q;
        q.push(root);
        vector<int> res;
        while(!q.empty()){
            int n = q.size(), maxs= INT_MIN;
            for(int i = 0; i < n; i++){
                TreeNode* node = q.front();
                q.pop();
                maxs = max(maxs, node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.push_back(maxs);
        }
        return res;
    }
};

剑指 Offer II 045. 二叉树最底层最左边的值

和上题类似，毫无含金量

bfs

class Solution {
public:
  int findBottomLeftValue(TreeNode* root) {
      int ret;
      queue<TreeNode*> q;
      q.push(root);
      while(!q.empty()){
          int n = q.size();
          for(int i = 0; i < n ; i++){
              TreeNode* node = q.front();
              q.pop();
              if(i == 0) {
                  ret = node->val;
              }
              if(node->left) q.push(node->left);
              if(node->right) q.push(node->right);
          }
      }
      return ret;
  }
};

dfs

注意height初始值为-1,因为如果只有根节点的时候能够赋值ret

class Solution {
private:
int ret, height = -1;
public:
  int findBottomLeftValue(TreeNode* root) {
      dfs(root, 0);
      return ret;
  }
  void dfs(TreeNode* root, int g){
      if(!root) return;
      if(g > height) {
          ret = root->val;
          height = g;
      }
      dfs(root->left, g + 1);
      dfs(root->right, g + 1);
      return ;
  }
};

剑指 Offer II 046. 二叉树的右侧视图

上一题的变种

class Solution {
public:
  vector<int> rightSideView(TreeNode* root) {
      if(!root) return {};
      queue<TreeNode*> q;
      q.push(root);
      vector<int> ret;
      while(!q.empty()){
          int n = q.size();
          for(int i = 0; i < n; i++){
              TreeNode* node = q.front();
              q.pop();
              if(i == 0) {
                  ret.push_back(node->val);
              }
              if(node->right) q.push(node->right);
              if(node->left) q.push(node->left);
          }
      }
      return ret;
  }
};