每日leetcode第0009天 0456. 132 Pattern

这是一道有难度的栈的题目。

难也在想不到为什么用栈来解决问题。

直觉上先想到将右值调到更大,要右值更大那么中值也要更大。

直觉上只需要一个尽可能大的中值和尽可能大的右值,就用两个变量。

但是想到了一个情况3 5 4 6 1我们先找到中值6,右值1。

但5和4都放不进中值,也无法放入右值。我们的3在右值为1的时候就无法成为合格左值。

而我们使用栈就可以解决这个问题,我们可以将有可能产生的右值和中值都压入单调栈。

将每个弹出元素弹出前,判断是否可能成为更大的右值。

例如6进栈,栈内为6,1为最大右值。

4进栈,栈内为4和6,1为最大右值。

5进栈前,4弹出,4为最大右值。栈内为5和6。

3比最大右值要小,输出true。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。