leetcode 435. Non-overlapping Intervals | 435. 无重叠区间（单调栈）

我就是我 2022-09-04 02:55 153阅读 0赞

## 题目 ##

[https://leetcode.com/problems/non-overlapping-intervals/][https_leetcode.com_problems_non-overlapping-intervals]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

我一开始是没有 get 到这道题的精髓的。只是在想，用贪心法，当两个 (a,b) pair 重叠时，删除 b 较大的就可以了，直到遍历完整个数组。

开始时只是维护了双指针在数组中游荡，分别叫 slow 和 fast。如果删 slow，则 slow 回退；如果删 fast，则 fast 前进。后来发现，指针是不能够随意回退的，因为你不能保证前面一个位置的元素仍然存在，可能早已被删除了。

那么在 slow 回退的时候，怎么能找到前一个元素呢？一种方法是维护一个 alive 数组，这种方法太矬了。另一种方法就是维护一个栈。于是突然发现，这不就是一个单调栈吗。。只不过是数组中对角线的两个数字单调而已。

附上草稿记录无效思考过程。。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

class Solution { 
        public int eraseOverlapIntervals(int[][] arr) { 
            int L = arr.length;
            Arrays.sort(arr, (o1, o2) -> { 
                if (o1[0] != o2[0]) return o1[0] - o2[0];
                else return o1[1] - o2[1];
            });
            
            // 居然是个单调栈？？？
            Stack<int[]> stack = new Stack<>();
            int i = 0;
            while (true) { 
                while (i < L && !stack.isEmpty() && stack.peek()[1] > arr[i][0]) { 
                    if (stack.peek()[1] > arr[i][1]) {  // 删slow
                        stack.pop();
                    } else {  // 删fast
                        i++;
                    }
                }
                if (i >= L) break;
                stack.push(arr[i++]);
            }
            return L - stack.size();
        }
    }

[https_leetcode.com_problems_non-overlapping-intervals]: https://leetcode.com/problems/non-overlapping-intervals/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/91640ca9242f4e36b4c68657d34c1a48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/24e2bab7a39a44909eb4de237483c0bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/db7d10447b5a4cf68a339e13c938e18c.png