栈结构使用场景

一、 根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置0来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。 解题关键: 实际上就是找当前元素 从[i,TSize] 找到大于该元素时. 数了几次. 首先最后一个元素默认是0,因为它后面已经没有元素了.

解法一： 1. 从左到右开始遍历,从第一个数到最后一个数开始遍历. 最后一个数因为后面没有元素,默认是0,不需要计算;

 2. 从[i+1,TSize]遍历,每个数直到找到比它大的数,数的次数就是对应的值;

 思路:

 1.创建一个result 结果数组.

 2.默认reslut[TSize-1] = 0;

 3.从0个元素遍历到最后一个元素[0,TSize-1];

    A.如果当前i >0 并且当前的元素和上一个元素相等,则没有必要继续循环. 则判断一下result[i-1]是否等于0,如果等于则直接将result[i] = 0,否则将result[i] = result[i-1]-1;

    B.遍历元素[i+1,TSize]

        如果当前T[j]>T[i],则result[i] = j-i;

        如果当前T[j]已经是最后一个元素,则默认result[i] = 0;

算法如下：

解法二：

解法三：

 思路:

 1. 初始化一个栈(用来存储索引),value数组

 2. 栈中存储的是元素的索引值index;

 3. 遍历整个温度数组从[0,TSize];

    (1).如果栈顶元素<当前元素,则将当前元素索引index-栈顶元素index,计算完毕则将当前栈顶元素移除,将当前元素索引index 存储到栈中; 出栈后,只要栈不为空.继续比较,直到栈顶元素不能满足T[i] > T[stack_index[top-1]]

 (2).如果当前的栈为空,则直接入栈;

 (3).如果当前的元素小于栈顶元素,则入栈

 (4).while循环结束后,当前元素也需要入栈;

二、  假设表达式中允许包含两种括号:圆括号与方括号,其嵌套顺序随意,即([]()) 或者[([][])]都是正确的.而这  [(]或者(()])或者([()) 都是不正确的格式. 检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述. 例如,考虑以下括号的判断:    [ ( [ ] [ ] ) ]；

算法：

思路:

 1. 将第0个元素压栈

 2. 遍历[1,strlen(data)]

    (3). 取栈顶字符

    (4). 检查该字符是左括号("(","[")

         a.是左"(",则判断紧接其后的data[i]是为右")"

            YES->压栈,NO->出栈

         b.是左"[",则判断紧跟其后的data[i]是为右"]"

            YES->压栈,NO->出栈

         c.表示式如果以"#"结尾,则判断紧跟其后的data是为左"(""]"

            YES->压栈,NO->-1;

 3.遍历结束,则判断栈是否为空,为空则表示匹配成功;否则匹配失败;

 [ ( [ ] [ ] ) ]

 1 2 3 4 5 6 7 8

三、杨辉三角

算法：

四、假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有 多少种不不同的⽅方法可以爬到楼顶呢?注意:给定 n 是一个正整数

算法如下

五、 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

 例如:

 s = "3[a]2[bc]", 返回 "aaabcbc".z

 s = "3[a2[c]]", 返回 "accaccacc".

 s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

 思路:

 例如:12[a]为例;

 1.遍历字符串 S

 2.如果当前字符不为方括号"]" 则入栈stack中;

 2.如果当前字符遇到了方括号"]" 则:

 ① 首先找到要复制的字符,例如stack="12[a",那么我要首先获取字符a;将这个a保存在另外一个栈去tempStack;

 ② 接下来,要找到需要备份的数量,例如stack="12[a",因为出栈过字符"a",则当前的top指向了"[",也就是等于2;

 ③ 而12对于字符串是2个字符, 我们要通过遍历找到数字12的top上限/下限的位置索引, 此时上限curTop = 2, 下限通过出栈,top = -1;

 ④ 根据范围[-1,2],读取出12保存到strOfInt 字符串中来, 并且将字符"12\0",转化成数字12;

 ⑤ 当前top=-1,将tempStack中的字符a,复制12份入栈到stack中来;

 ⑥ 为当前的stack扩容, 在stack字符的末尾添加字符结束符合'\0';