标签归档:stack

Leetcode 232. Implement Queue using Stacks(两个栈实现队列)

没什么卵用的东西,就是弄两个栈,再加入元素的时候辅助栈帮助实现逆序的过程,然后在加回去。。。

uva 442 Matrix Chain Multiplication(栈)

Description

Suppose you have to evaluate an expression like A*B*C*D*E where A,B,C,D and E are matrices. Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. However, the number of elementary multiplications needed strongly depends on the evaluation order you choose.

For example, let A be a 50*10 matrix, B a 10*20 matrix and C a 20*5 matrix. There are two different strategies to compute A*B*C, namely (A*B)*C and A*(B*C).

The first one takes 15000 elementary multiplications, but the second one only 3500.

Your job is to write a program that determines the number of elementary multiplications needed for a given evaluation strategy.

Input Specification

Input consists of two parts: a list of matrices and a list of expressions.

The first line of the input file contains one integer n ( tex2html_wrap_inline28 ), representing the number of matrices in the first part. The next n lines each contain one capital letter, specifying the name of the matrix, and two integers, specifying the number of rows and columns of the matrix.

The second part of the input file strictly adheres to the following syntax (given in EBNF):

Output Specification

For each expression found in the second part of the input file, print one line containing the word “error” if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multiplications needed to evaluate the expression in the way specified by the parentheses.

Sample Input

Sample Output

计算出一个矩阵相乘的表达式中乘法操作的次数。
我们可以用一个栈来处理表达式。

 

hdu 1506 Largest Rectangle in a Histogram(动态规划或者单调栈)

Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, …, hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000 0

Sample Output

8
4000

有两种思路:我一开始想的是对于每一块木板来说,它都有两个性质:即从他开始向左延伸能到达的最左边的那块木板的位置l,以及向右延伸能到达的最右边那块木板的位置r。

那么我们只需要从1-n比较每一块相邻木板的长度:如果当前木板的长度小于它左边界的之前的那一块木板的长度,那么他的左边界一定可以到达左边界之前那块木板的左边界(好拗口)。但是画一个图就会很明显了。右边也是这个道理。

为了减少更新的次数,左边采用的是1-n,右边采用的是n-1的方向。

dp思路的代码:

第二种思路是网上看到的,引入了一个我之前不知道的概念:单调栈

单调栈:就是栈内元素具有单调性,包括单调递增栈和单调递减栈。其实单调递增(减)栈就是每次碰到比栈顶元素小(大)的就出栈,保持栈里元素的单调性。

那对于这道题目而言,我们需要维护一个从左到右的单调递增栈,和一个从右到左的单调递增栈即可。

开两个数组l,r分别记录i号位置的木板向左(包含自己),向右延伸的距离。