Open
Description
线下课陈皓老师讲了做算法题的方法：
- 要画图；
- 可以先用最常规的方法实现，然后再一步一步的优化；
在做LeetCode 503 https://leetcode-cn.com/problems/next-greater-element-ii/ 时，
我有了深刻的体会。
最初这道题是用数组中当前元素直接和后面元素比较的方法做的。但是作业要求是用栈，
我想了大半天也没想明白怎么能用栈来解决这个问题。
无奈之下求助了一下网络，看到了几种方法，也基本没看懂。然后就又开始怀疑自己的智商。
不过，最终还是静下心来，按陈皓老师的方法开始尝试。
1.常规逻辑分析，不考虑效率
我写了一个比较长的用例，然后开始在上面画图，这回总算是看出来怎么引入堆栈了，过程如下：
// 遍历数组，每个数都和其后面的数据比较，直到循环回到自己的位置
// 100, ---25,---11,---1,---110,---109
// 当前值--小---小---小---大
// 那么[当前值 -> 110] 之间的数据，就应该用110替换。
// 可以用栈来暂存这些数据。栈空表明区间内的所有数据都替换完成
之前一直没看出来是因为自己只选了个3元素的用例，在上面画没看出这种效果。以后不能再犯这样的错误了。
按照上面的图，写了分析：
- 入栈情况：
- i < len, A[i] <= peek()
- i < len, 栈空
- 出栈情况：
- 栈不空，a[i] > peek()
- a[i] <= peek() 停止出栈
- 当前元素a[i]，可能需要进栈，所以将入栈的判断放在出栈操作之后。
接着就有了下面的代码：
for (int i = 0; i < 2 * len; i++) {
int ii = i % len;
// 出栈条件判断
if (!stack.isEmpty() && nums[ii] > nums[stack.peek()]) {
while (!stack.isEmpty()) {
// 当前值不再大于栈顶值结束出栈
if (nums[ii] <= nums[stack.peek()]){
break;
}
rst[stack.pop()] = nums[ii];
}
}
// 入栈条件判断
// 由于当前元素可能导致出栈操作，所以要等出栈完成后，再做入栈判断
if (i < len && stack.isEmpty()) {
stack.push(ii);
continue;
}
if (!stack.isEmpty() && nums[ii] <= nums[stack.peek()]) {
if (i < len) {
stack.push(ii);
}
}
}
2.优化代码
leetcode提交测试通过后开始优化，于是有了下面的这个版本
for (int i = 0; i < 2 * len; i++) {
int ii = i % len;
// 出栈条件判断
if (!stack.isEmpty() && nums[ii] > nums[stack.peek()]) {
while (!stack.isEmpty()) {
// 值相等结束出栈
if (nums[ii] <= nums[stack.peek()]){
break;
}
rst[stack.pop()] = nums[ii];
}
}
// 入栈条件判断
if (i < len){
stack.push(ii);
}
}
看了看 if (!stack.isEmpty() 和 while (!stack.isEmpty())可以合并，
于是又了下面这个版本
for (int i = 0; i < 2 * len; i++) {
int ii = i % len;
// 出栈条件判断
while (!stack.isEmpty() && nums[ii] > nums[stack.peek()]) {
rst[stack.pop()] = nums[ii];
}
// 入栈条件判断
if (i < len){
stack.push(ii);
}
}
这个版本我前面在网上看到了，但绞尽脑汁也没看明白。自己是思维跳不了那么远。
如果不是陈老师的方法，我估计只能接受被这道算法题摧残的结果了。现在总算开点窍了。
真心感谢陈皓老师，感谢极客！
Metadata
Metadata
Assignees
Labels
No labels