56. 合并区间(思维)

• 2020 年 2 月 17 日
• 筆記

题目链接：https://leetcode-cn.com/problems/merge-intervals/

       用了各种stl去模拟这个过程，写的太麻烦了，之后看了别人的做法确实要好写一点，但是思路都是差不多的，首先对数组按左端点从小到大排序，然后枚举每个区间，去比较当前区间的右端点的值是否大于等于下一个区间的左端点的值，然后判断并更新区间，然后保存答案。这里合并的过程我用栈去实现的，那么获取答案就还要另外的花费时间去存到vector中，而且栈存的答案是倒叙的，最终反转数组又要花费时间，所以效率不高。还是别人的做法比较可取，直接用临时变量来代替栈顶元素。

AC代码：

class Solution {  public:      vector<vector<int>> merge(vector<vector<int>>& intervals) {          vector<vector<int>> ans;          stack<pair<int, int>> s;          int len = intervals.size();          if(len == 0) return ans;          typedef pair<int, int> p;          vector<pair<int, int>> v;          for (int i = 0; i < len; i++) {              v.push_back(p(intervals[i][0], intervals[i][1]));          }          sort(v.begin(), v.end(), [](const pair<int, int> a, const pair<int, int> b) {              if (a.first == b.first) return a.second < b.second;              return a.first < b.first;              });          s.push(p(v[0].first, v[0].second));          for (int i = 1; i < len; i++) {              if (s.top().second >= v[i].first) {                  pair<int, int> tmp = p(min(s.top().first,v[i].first), max(v[i].second, s.top().second));                  s.pop();                  s.push(tmp);              }              else {                  pair<int, int> tmp = p(v[i].first, v[i].second);                  s.push(tmp);              }          }          while(s.size() != 0) {              vector<int> x{ s.top().first, s.top().second };              ans.push_back(x);              s.pop();          }          reverse(ans.begin(), ans.end());          return ans;      }  };