piling up

Problem

There is a horizontal row of cubes. The length of each cube is given. You need to create a new vertical pile of cubes. The new pile should follow these directions: if cubei is on top of cubej then sidelengthi>=sidelengthj.

When stacking the cubes, you can only pick up either the leftmost or the rightmost cube each time. Print “Yes” if it is possible to stack the cubes. Otherwise, print “No”. Do not print the quotation marks.

从这给定的n个正方体中的最左边或者最右边拿一个正方体放置将他们摞起来，要保证下面的正方体边长比上面的大。此时可以连续两次从一侧拿。

Input Format

The first line contains a single integer T, the number of test cases.
For each test case, there are 2 lines.
The first line of each test case contains n, the number of cubes.
The second line contains n space separated integers, denoting the sideLengths of each cube in that order.

Constraints

1<=T<=5
1<=n<=10⁵
1<=sidelength<=2³¹

Output Format

For each test case, output a single line containing either “Yes” or “No” without the quotes.

Sample Input

2
6
4 3 2 1 3 4
3
1 3 2

Sample Output

Yes
No

Explanation

In the first test case, pick in this order: left - 4, right -4 , left -3 , right -3 , left -2 , right - 1.
In the second test case, no order gives an appropriate arrangement of vertical cubes. 3 will always come after either 2 or 1.

代码

基本思路：尽可能地把边长大的正方体放在底层

t=int(input())
for _ in range(t):
    n=int(input())
    ans='Yes'
    ls=list(map(int,input().split()))
    l=0
    r=n-1
    bound=max(ls[l],ls[r])
    while l<=r:
        if ls[l]>ls[r]:
            if ls[l]>bound:
                ans='No'
                break
            bound=max(ls[l],bound) #等价于bound=max(ls[l],ls[r])
            l+=1

        else:
            if ls[r]>bound:
                ans='No'
                break
            bound=max(bound,ls[r])  #等价于bound=max(ls[l],ls[r])
            r-=1
    print(ans)

• 注意bound一定要在l,r变化前重置，作为l,r位置移动后的判断基准

优化

    t = int(input())
    for i in range(0, t):
        n = int(input())
        lst = list(map(int, input().split()))
        min_index = lst.index(min(lst))  #得到最小值的index
        left = lst[ : min_index]
        right = lst[min_index : ]
        if left == sorted(left, reverse = True) and right == sorted(right, reverse = False):
            print("Yes")
        else:
            print("No")     

• 以最小边长为界，左侧边长递减，右侧边长递增

  类似地

    while i < l - 1 and lst[i] >= lst[i+1]:  #左侧i递减才能使i移动到最小元素
        i += 1
    while i < l - 1 and lst[i] <= lst[i+1]:  #右侧i递增才能使i移动到最后
        i += 1
    print "Yes" if i == l - 1 else "No"