力扣K神图解算法数据结构解析02

力扣K神图解算法数据结构点这里

二、模拟

1. 剑指29，顺时针打印矩阵

   //时间O(mn)，空间O(mn)
   //模拟，定义四个边界，每遍历一行就收缩一次边界，同时注意跳出循环边界条件
   class Solution {
   public:
       vector<int> spiralOrder(vector<vector<int>>& vec) 
       {
           if(vec.empty()) return {};
           vector<int> res;
           int left = 0;
           int top = 0;
           int right = vec[0].size()-1;
           int bottom = vec.size()-1;
           while(1)
           {
               //1
               for(int i=left;i<=right;++i)
               {
                   res.push_back(vec[top][i]);
               }
               if(++top > bottom) break;
               //2
               for(int i=top;i<=bottom;++i)
               {
                   res.push_back(vec[i][right]);
               }
               if(--right < left) break;
               //3
               for(int i=right;i>=left;--i)
               {
                   res.push_back(vec[bottom][i]);
               }
               if(--bottom < top) break;
               //4
               for(int i=bottom;i>=top;--i)
               {
                   res.push_back(vec[i][left]);
               }
               if(++left > right) break;
           }
           return res;
       }
   };
              

2. 剑指31，栈的push/pop

   //时间O(n)，空间O(n)
   //使用辅助栈模拟push和pop操作，始终比较st.top()是否和出栈元素顺序一致
   //一致则pop，否则继续push，当push越界时判定false，否则true
   class Solution {
   public:
       bool validateStackSequences
       (vector<int>& vec1, vector<int>& vec2) 
       {
           size_t i = 0;
           size_t j = 0;
           stack<int> st;
           //当j=vec2.size()时跳出
           while(j < vec2.size())
           {
               //栈可能为空
               if(st.empty()) 
               {
                   if(i >= vec1.size()) return false;
                   st.push(vec1[i++]);
               }
               //当顺序一致时就pop
               if(st.top() == vec2[j])
               {
                   st.pop();
                   ++j;
               }
               //否则就push，直到越界
               else
               {
                   if(i >= vec1.size()) return false;
                   st.push(vec1[i++]);
               }
           }
           return true;
       }
   };