When encountering bracket validity, next larger element, specific minimum value, try stack

Yanjiang 2021-04-07 21:46:53
encountering bracket validity larger element


Recently I've been looking at data structures and algorithms , Try to sum up ~

TL;DR

The characteristics of the stack : First in, then out .

Often used to solve :

  • Bracket validity : Traverse , In case of left bracket, put it on the stack , Right parenthesis encountered , Matching is out of the stack , otherwise false. End of traversal , The stack value is false, Instead of true
  • The next big element series : Traverse backwards , Change the next unknown into the last known , Maintain the decrement stack , It's smaller than the top of the stack , Otherwise, it will be out of the stack
  • Smallest stack : commonly “ Space for time ”, Use the auxiliary stack

Circular array : Using the technique of redundancy , There is no actual expansion array , But when traversing , It's like traversing a circular array .

practice : Valid brackets

stack_21

The characteristic of a stack is : Last in, first out

For effectiveness , Because the left bracket encountered after must be closed first , So we can put the left bracket at the top of the stack , You can get out of the stack when you meet the right bracket , The feeling of Xiaole ~

Ideas : Traversal string , When I encounter the left bracket, I put it on the stack , Right parenthesis encountered , It doesn't match the elements at the top of the stack false, If it matches, it's out of the stack . After traversing , If the stack has elements , explain false, Instead of true.

// It's more semantic 
const top = (stack) => stack[stack.length - 1];
function isValid(s) {
let stack = [];
// Dictionaries store pairing information 
let dict = {
"{": "}",
"[": "]",
"(": ")",
};
for (let i = 0; i < s.length; i++) {
let cur = s[i];
// Is it the left bracket 
const isLeft = cur in dict;
// Left bracket in stack 
if (isLeft) stack.push(cur);
// Right bracket , Check with the top of the stack , Yes, it's out of the stack , Not so false
else {
const isPair = dict[top(stack)] === cur;
if (!isPair) return false;
stack.pop();
}
}
// End of traversal , If there are elements in the stack, they are false, Conversely true
return !stack.length;
}
 Copy code 

Space is O(n), Time, too O(n)

May have a look Official explanation

practice : Next bigger element 1

stack_22

The violent solution to this problem is very good , It's just scanning the back of each element , Just find the first larger element . But the time complexity of the brute force solution is O(n^2).

The next bigger problem of this kind You can think abstractly like this : Think of the elements of an array as people standing side by side , Element size imagine the height of an adult . These people stand in a line in front of you , How to find elements 「2」 Of Next Greater Number Well ? It's simple , If you can see the elements 「2」, So the first person behind him is 「2」 Of Next Greater Number, Because than 「2」 Small elements are not tall enough , All be 「2」 It's in the way , The first thing that comes out is the answer .

stack_23

The next big element series : You can use the same set of ideas and templates

  • Traverse backwards , Change the next unknown into the last known
  • Maintain the decrement stack , Meet someone bigger than the top of the stack , The top of the stack , Until you meet someone smaller than the top of the stack or the stack is empty , Push
const top = (arr) => arr[arr.length - 1];
// [1,4,6,2] => {1:4,4:6,6:-1,2:-1}
var _nextGreaterElement = function (arr) {
// Decrement stack 
let stack = [];
// Answer storage , It depends on the topic 
let res = {};
// Traverse backwards 
for (let i = arr.length - 1; i >= 0; i--) {
let cur = arr[i];
// Maintain the decrement stack , Meet someone bigger than the top of the stack , The top of the stack , Until you meet someone smaller than the top of the stack or the stack is empty , Put the answer and current value on the stack 
while (stack.length && cur >= top(stack)) {
stack.pop();
}
// Store answers , It depends on the topic 
res[i] = stack.length ? top(stack) : -1;
stack.push(cur);
}
return res;
};
var nextGreaterElement = function (nums1, nums2) {
const res = _nextGreaterElement(nums2);
return nums1.map((item) => res[item]);
};
 Copy code 

So the time complexity is O(m+n), The complexity of space is also O(m+n)

Monotonous stack solution Next Greater Number A class of questions

practice : Next bigger element 2

stack_24

This question is more complicated than the one just now , On the loop array .

This kind of problem , In fact, a little change in thinking is good ~

[1,4,3] => In the case of circular arrays => [1,4,3,1,4,3]

But you don't really need to expand arrays like this , Use the little technique of surplus collection , The number of iterations is twice the number of arrays , however cur The value is arr[i%len]

And still use the above ideas , however , To store answers here, you just need to start at the actual length .

const top = (arr) => arr[arr.length - 1];
var nextGreaterElements = function (nums) {
// Decrement stack 
let s = [];
// It is stored here according to the topic , This problem can be solved by array 
let ans = [];
const len = nums.length;
// Reverse traversal , The length of the array becomes 2 It's twice as long 
for (let i = len * 2 - 1; i >= 0; i--) {
// Calculate the current value with the remainder operation , On the surface, it looks like it's actually traversing a circular array 
let cur = nums[i % len];
while (s.length && cur >= top(s)) {
s.pop();
}
// At the length of the actual array , Start storing answers 
i < len && (ans[i] = s.length ? top(s) : -1);
s.push(cur);
}
return ans;
};
 Copy code 

Time complexity and space complexity are both O(n)~

Monotonous stack solution Next Greater Number A class of questions

Give it a quick try : Daily temperature

Please according to the daily The temperature list , Rebuild a list . The output of the corresponding position is : To see a higher temperature , At least the number of days to wait . If the temperature doesn't rise after that , Please use... In this position  0 Instead of .

for example , Given a list  temperatures = [73, 74, 75, 71, 69, 72, 76, 73], Your output should be  [1, 1, 4, 2, 1, 1, 0, 0].

const top = (arr) => arr[arr.length - 1];
var dailyTemperatures = function (T) {
let s = [];
let res = [];
for (let i = T.length - 1; i >= 0; i--) {
const cur = T[i];
while (s.length && cur >= T[top(s)]) {
s.pop();
}
// As the case may be , The number of days is calculated here , Obviously, storage i appropriate 
res[i] = s.length ? top(s) - i : 0;
s.push(i);
}
return res;
};
 Copy code 

practice : Smallest stack

stack_25

A little bit of trouble here is ,getMin, The violence law must be easy , But time complexity O(n), Want to be O(1).

Another way of thinking , Every time push When , In addition to storing data , And maintain the minimum stack ( Auxiliary stack ), The top of the stack is the smallest element of the current array ;pop When , Top of stack element pop up .

155_fig1.gif

function Stack(){
this.data = []
this.helpStack = []
}
Stack.prototype.push = num => {
this.data.push(num)
this.helpStack.push(num<this.data[this.data.length-1]?num:this.data[this.data.length-1])
}
Stack.prototype.pop = () => {
this.data.length && this.data.pop()
this.helpStack.length &&this.helpStack.pop()
}
Stack.prototype.getMin = () => {
return this.helpStack[this.helpStack.length-1]
}
 Copy code 

Of course, this is the idea of synchronization stack , Different steps , Personally, I think it's a little complicated , Those who are interested can continue to study ~

Official animation

quote

版权声明
本文为[Yanjiang]所创,转载请带上原文链接,感谢
https://qdmana.com/2021/04/20210407213623127q.html

  1. Behind the miracle of the sixth championship is the football with AI blessing in the Bundesliga
  2. An easy to use Visual Studio code extension - live server, suitable for front-end gadget development
  3. 用 Python 抓取公号文章保存成 HTML
  4. User login of front end spa project based on Vue and Quasar (2)
  5. Summary of common selectors in CSS
  6. Using Python to grab articles with public number and save them as HTML
  7. To "restless" you
  8. 【免费开源】基于Vue和Quasar的crudapi前端SPA项目实战—环境搭建 (一)
  9. 【微信小程序】引入阿里巴巴图标库iconfont
  10. layui表格点击排序按钮后,表格绑定事件失效解决方法
  11. Unity解析和显示/播放GIF图片,支持http url,支持本地file://,支持暂停、继续播放
  12. 【vue】 export、export default、import的用法和区别
  13. [free and open source] crudapi front end spa project based on Vue and Quasar
  14. [wechat applet] introduces Alibaba icon library iconfont
  15. Layui table click Sort button, table binding event failure solution
  16. Element树形控件Tree踩坑:修改current-node-key无效
  17. Unity parses and displays / plays GIF images, supports HTTP URL, supports local file: / /, supports pause and resume playback
  18. Element树形控件Tree踩坑:修改current-node-key无效
  19. The usage and difference of export, export default and import
  20. Element tree control: invalid to modify current node key
  21. Element tree control: invalid to modify current node key
  22. linux下安装apache(httpd-2.4.3版本)各种坑
  23. How to install Apache (httpd-2.4.3) under Linux
  24. 程序员业余时间写的代码也算公司的?Nginx之父被捕引发争议
  25. Nacos serialize for class [com.alibaba.nacos.common.http.HttpRestResult] failed.
  26. Do programmers write code in their spare time? Controversy over the arrest of nginx's father
  27. Nacos serialize for class [ com.alibaba.nacos . common.http.HttpRestResult ] failed.
  28. Seamless management of API documents using eolink and gitlab
  29. vue 的基础应用(上)
  30. 28岁开始零基础学前端,这些血的教训你一定要避免
  31. Basic application of Vue
  32. Starting at the age of 28, you must avoid these bloody lessons
  33. Ubuntu 16.04 can not connect to the wireless solution and QQ installation
  34. Industry security experts talk about the rapid development of digital economy, how to guarantee the security of data elements?
  35. 利用Vue实现一个简单的购物车功能
  36. Behind the "tireless classroom" and teacher training, can byte education really "work wonders"?
  37. Using Vue to realize a simple shopping cart function
  38. 【css】伪类和伪类元素的区别
  39. 【css效果】实现简单的下拉菜单
  40. 【vue】父子组件传值
  41. The difference between pseudo class and pseudo class elements
  42. [CSS effect] simple drop-down menu
  43. [Vue] value transfer by parent-child component
  44. 【css】设置table表格边框样式
  45. 【css】修改input,textarea中的placeholder样式
  46. vue-router的两种模式(hash和history)及区别
  47. CSS3的滤镜filter属性
  48. [CSS] set table border style
  49. [CSS] modify the placeholder style in input and textarea
  50. Two modes of Vue router (hash and History) and their differences
  51. Filter property of CSS3
  52. 全局安装gulp 报错问题解决
  53. Solution of error report in global installation of gulp
  54. 18个好用的自定义react hook
  55. 你应该知道的常用服务器HTTP状态码?
  56. 18 user defined react hooks
  57. What HTTP status codes should you know about common servers?
  58. 手把手教你打造属于自己团队的前端小报系统
  59. Hand in hand to teach you to build your own front-end tabloid system
  60. In 2021, enterprise SEO actual operation, how to less update, batch ranking regional words?