转自 https://www.twblogs.net/a/5cba6cd4bd9eee0eff45f091/zh-cn
原創MeggieYue2019-04-20 08:50
刷题时间： 2019/04/15 – 2019/04/19
主播：yxc(闫雪灿)
题号 | 题目 | 链接
69 | Sqrt(x) | https://leetcode.com/problems/sqrtx/
34 | Find First and Last Position of Element in Sorted Array | https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
74 | Search a 2D Matrix | https://leetcode.com/problems/search-a-2d-matrix/
153 | Find Minimum in Rotated Sorted Array | https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
162 | Find Peak Element | https://leetcode.com/problems/find-peak-element/
155 | Min Stack | https://leetcode.com/problems/min-stack/
496 | Next Greater Element I | https://leetcode.com/problems/next-greater-element-i/
42 | Trapping Rain Water | https://leetcode.com/problems/trapping-rain-water/
84 | Largest Rectangle in Histogram | https://leetcode.com/problems/largest-rectangle-in-histogram/
475 | Heaters | https://leetcode.com/problems/heaters/
239 | Sliding Window Maximum | https://leetcode.com/problems/sliding-window-maximum/
456 | 132 Pattern |
No.69 求一个数开根号的值，向下取整。（AC）
- 二分问题。
- 在本问题中，
target * 1ll * target <= x， 即最小值最大是…的问题，可以根据不等式确定判断函数中的符号，确定是第二种模板。 - 二分经典模板 https://www.acwing.com/blog/content/31/
版本1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
C++ 代码模板：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
版本2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。
C++ 代码模板：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
以上代码中，
版本1（mid = l + r >> 1）对应：最大值最小是…的问题
版本2 (mid = l + r + 1 >> 1) 对应： 最小值最大是…的问题
No.34 Find First and Last Position of Element in Sorted Array (AC)
- 二分问题
- 分别二分出一个数字第一次和最后一次出现的位置，判断套件中的符号按照上一题的总结来写。
- 找出现的第一个位置时， 是
nusm[i] >= target，由此确定判断条件；找最后一个位置时，是nums[i] <= target，由此确定判断条件。
No.74 Search a 2D Matrix (AC)
- 从左下角活右上角开始遍历，每次删掉一行或一列。O(m + n)
- 二分来做。因为二维展成一维之后是严格递增的。
- 需要注意的是，一维座标转换成二维座标时除的是列的值
No.153 Find Minimum in Rotated Sorted Array (AC)
- 二分来做。
- 二分条件是
target < nums[0]，这也是我们要找的数需要满足的条件。这里不能取等号，可以多测试几个样例。 - 没有旋转的数组（整体呈现升序）边界条件要特判，不符合我们的二分条件。
No.162 Find Peak Element （AC）
- 线性做法，从前往后扫描，两边边界特判
- 二分来做。需要分析清楚的是，若nums[mid] < nums[mid + 1],则右边一定存在峰值，否则左边一定存在峰值。
No.155 Min Stack(AC)
- 用一个辅助栈存储栈内每个元素的最小值
- 需要判辅助栈为空的边界条件
No.496 Next Greater Element I (AC)
- 用单调栈来做。
- 维护一个单调递增的栈，从后往前开始扫描
- 栈为空的情况需要特判
No.42 Trapping Rain Water (AC)
- 分别计算每一个柱子可装的水是多少，这个值由该柱子左右两边最高的柱子中相对矮的一根柱子决定，即
w[i] = min(left_max[i], right_max[i]) - height[i]，若w[i]的值小于0， 则取0； - 分别从前后扫描两遍，得到左边和右边的最大值。
- 再遍历一遍统计结果。
- 也可以用单调栈进一步优化，参考 https://www.acwing.com/solution/LeetCode/content/121/
No.84 Largest Rectangle in Histogram (AC)
- 单调栈来做
- 长方体的最大面积由它可延伸的面积决定，即要找到一根柱子它的左边和右边第一个比它矮的柱子的索引。
- 前后遍历两次，维护两个单调栈
No.475 Heaters (WA–>AC)
- 二分找到每个房屋到暖气的最近距离，然后输出所有距离的最大值
- 为了避免比houses当前索引更大/小的值在heaters中找不着，一开始在heaters数组中插入一个INT_MIN, INT_MAX，然后对heaters数组排序。
- 一开始的思路：求两个暖气片之间的最大距离，然后一头一尾的暖气片特殊处理，这里会存在的问题是，当有若干个暖气片远大于房屋的最大索引时，就会出问题。这个方法容易写出bug，不是一个很好的方法。
No.239 Sliding Window Maximum (AC)
- 本题需要维护一个双向队列deque，选择数据结构时要想清楚。
- 当对头元素失效，删除
dq.pop_front()；若当前元素大于对位元素，则循环删除对位元素dq.pop_back()。 - 只有当前遍历元素的索引大与等于滑动窗口的长度K时才开始记录答案。
queue和deque数据结构比较及相关操作
queue数据结构
特点： 先进先出，只能从队尾添加元素，队头删除元素
queue<int> q; // 创建
q.empty(); // 判空
q.size(); // 队列大小
q.push(s); // 从队尾新增元素
q.pop(); // 从队头删除元素
q.front(); // 返回队头元素的值
q.back(); // 返回队尾元素的值
deque数据结构
特点： 双端队列，可以在队头和队尾分别进行插入和删除操作
deque<int> dq; // 创建
dq.empty(); // 判空
dq.size(); // 队列大小
dq.clear(); // 清空双端队列
dq.push_back(s); // 从队尾新增元素
dq.push_front(); // 从队头新增元素
dq.back(); // 返回队尾元素
dq.front(); // 返回队头元素
dq.pop_back(); // 删除队尾元素
dq.pop_front(); // 删除队头元素
No.456 132 Pattern (AC)
- 单调栈来做
- 从后往前枚举，维护一个单调递增栈。
- 需要记录ak的最大值。因为ai< ak < aj (i < j < k),所以在枚举过程中，ak一定会被弹出栈，因此ak的最大值是弹出栈的元素中的最大值。
- 若当前枚举元素小于ak,则满足132模式的子序列已找到。
- 若从前往后枚举，则ak是否入栈不好判断。