353. Design Snake Game

After visiting the top rated solutions, I know all we need to do is to maintain a double linked queue. Every move, we get the front node's row index and column index. Then we compute the new front's row and column index. And we also need to pop out the tail node. If the new front node is valid, i.e. it is in the board and also it doesn't hit the snake. Then the question is how to know if it hits the snake? This can be done by hash set. The hash set caches all the nodes' positions. As long as the new node can be found in the hash set, we know it hits the snake itself. Since we have a hash set to keep all the nodes' position, whenever we remove/insert a new node from/into the queue, we need to erase/insert it from/into the hash set too. Note, we need to remove the tail BEFORE checking otherwise the snake is one longer than it should be. If the new node is valid, we push the new node to the front and insert it into hash set. And then we check if the new node hits a food. If so, we increment the score and we push the tail back to the queue back.

When I revisited this problem, I missed line 35. It's important to check the index before accessing an array.

1:  class SnakeGame {  
2:  private:  
3:    int w, h, i;  
4:    deque<pair<int, int>> q;  
5:    vector<pair<int, int>> f;  
6:    set<pair<int, int>> s;  
7:  public:  
8:    /** Initialize your data structure here.  
9:      @param width - screen width  
10:      @param height - screen height   
11:      @param food - A list of food positions  
12:      E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */  
13:    SnakeGame(int width, int height, vector<pair<int, int>> food) {  
14:      w = width, h = height, i = 0;  
15:      f = food;  
16:      q.push_back(make_pair(0, 0));  
17:    }  
18:    /** Moves the snake.  
19:      @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down   
20:      @return The game's score after the move. Return -1 if game over.   
21:      Game over when snake crosses the screen boundary or bites its body. */  
22:    int move(string direction) {  
23:      pair<int, int> head = q.front();  
24:      pair<int, int> tail = q.back();  
25:      int r = head.first, c = head.second;  
26:      q.pop_back();  
27:      s.erase(tail);  
28:      if (direction == "U") r--;  
29:      else if (direction == "D") r++;  
30:      else if (direction == "R") c++;  
31:      else if (direction == "L") c--;  
32:      if (r < 0 || r == h || c < 0 || c == w || s.count(make_pair(r, c))) return -1;  
33:      q.push_front(make_pair(r, c));  
34:      s.insert(make_pair(r, c));  
35:      if (i == f.size()) return q.size()-1;  
36:      if (f[i].first == r && f[i].second == c) {  
37:        q.push_back(tail);  
38:        s.insert(make_pair(tail.first, tail.second));  
39:        i++;  
40:      }  
41:      return q.size()-1;  
42:    }  
43:  };  
44:  /**  
45:   * Your SnakeGame object will be instantiated and called as such:  
46:   * SnakeGame obj = new SnakeGame(width, height, food);  
47:   * int param_1 = obj.move(direction);  
48:   */  

239. Sliding Window Maximum

First of all, I tried to use priority_queue (i.e. heap) to solve the problem. The idea is that the priority queue maintains the valid maximum number in the window. Then the question will be when the maximum number is not valid? There will be two cases. One is the top of heap is less than the new number. The other is the top of heap is out of the window. So we need to keep two information in one heap node, i.e. number and its index (Well index should be sufficient as number can be identified by index). The heap should be sorted by the number value. Also, once we meet an invalid heap top, we need to keep popping out invalid top until we have one or the heap becomes empty. Then we can push the new number into heap. What if we see the heap top is valid? We just need to push the new number into heap because we'll deal with all invalid numbers later when we encounter an invalid heap top. With regard to the result, we just need to push the heap top to the result. The running time is O(NlogN).

1:  class Solution {  
2:  public:  
3:    vector<int> maxSlidingWindow(vector<int>& nums, int k) {  
4:      priority_queue<pair<int, int>> heap;  
5:      vector<int> res;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        if (i < k) heap.push(make_pair(nums[i], i));  
8:        else {  
9:          while (!heap.empty() && (heap.top().first < nums[i] || i - heap.top().second >= k)) heap.pop();  
10:          heap.push(make_pair(nums[i], i));  
11:        }  
12:        if (i >= k-1) {  
13:          res.push_back(heap.top().first);  
14:        }  
15:      }  
16:      return res;  
17:    }  
18:  };  

There is O(n) solution. This solution uses double linked queue. Similar idea as before, the queue's front always keep the index of valid maximum number in the window. So when the front's index is out of the window, we remove the front. And then we check the back of the queue. Since we just need to keep the possible maximum number in the queue, we can remove all the numbers less than the new number. This is the same idea as line 8 and 9 in solution above. Since all the numbers are only processed twice, the running time is O(2N). Such double linked queue is also called monotonic queue.

1:  class Solution {  
2:  public:  
3:    vector<int> maxSlidingWindow(vector<int>& nums, int k) {  
4:      deque<int> queue;  
5:      vector<int> res;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        if (!queue.empty() && queue.front() == i-k) queue.pop_front();  
8:        while (!queue.empty() && nums[queue.back()] <= nums[i]) queue.pop_back();  
9:        queue.push_back(i);  
10:        if (i >= k-1) res.push_back(nums[queue.front()]);  
11:      }  
12:      return res;  
13:    }  
14:  };