GOD_hj 有一把数字密码锁，但是他陷于 whk，没时间来开锁。这把锁从左到右有 nn 个数，组成了一个序列 \{a\}{a}。 由于 GOD_hj 的记性不好，所以只要将锁设置为输入任意单峰序列即可打开。具体为： a_1 \le \cdots \le a_i \ge a_{i+1} \ge \cdots \ge a_n\quad (1 \le i \le n) a 1 ​ ≤⋯≤a i ​ ≥a i+1 ​ ≥⋯≥a n ​ (1≤i≤n) GOD_hj 的锁是拨动

的，每次只能将一个数字上下拨动一格。现在问你：最少需要多少次拨动才能将锁打开？

注：单峰序列是指序列从左到右单调不降，从左到右单调不增的序列。

我的回答是：

先找到最大值的下标 $i$，然后分别从开头到 $i$ 和从结尾到 $i$ 找到单调不降的长度 $len1$ 和 $len2$，最终答案为 $n-\max(len1,len2)$。

时间复杂度 $O(n)$。

代码实现：

n = int(input())
a = list(map(int, input().split()))

i = a.index(max(a))
len1, len2 = 1, 1
for j in range(i-1, -1, -1):
    if a[j] <= a[j+1]:
        len1 += 1
    else:
        break
for j in range(i+1, n):
    if a[j] <= a[j-1]:
        len2 += 1
    else:
        break

print(n - max(len1, len2))

相关问题

w乘h乘n的张量X按模态1乘A1按模态2乘A2模态3乘A3的时间复杂度

### 回答1：
对于一个w乘h乘n的张量X，按照模态1乘A1、按照模态2乘A2、按照模态3乘A3的顺序进行乘积运算，假设A1为k1乘w的矩阵，A2为k2乘h的矩阵，A3为k3乘n的矩阵。则该乘积运算的时间复杂度为：

O(k1whk2hk3n)

即为O(k1k2k3nwh^2)

因此，该乘积运算的时间复杂度与矩阵A1、A2、A3的维度以及张量X的大小有关。

### 回答2：
求解张量 X 的时间复杂度可以通过计算每个模态的乘法运算次数来得到。设 X 的维度为 w×h×n，A1、A2 和 A3 的维度分别为 w1×w、h1×h 和 n1×n。

根据张量乘法的定义，对于每个模态的乘法，乘积中的两个张量的维度必须满足：前一个张量的维度等于后一个张量的轴长度，其中轴的长度对应于乘法运算中相乘的两个元素的次数。

所以，模态1 的乘法运算次数为 w1×w，模态2 的乘法运算次数为 h1×h，模态3 的乘法运算次数为 n1×n。

则整个张量 X 的时间复杂度为模态1 乘法运算次数与模态2 乘法运算次数与模态3 乘法运算次数的乘积。

总的时间复杂度为：
(w1×w) × (h1×h) × (n1×n) = w1×h1×n1 × w×h×n

因此，X 按模态1 乘 A1 按模态2 乘 A2 按模态3 乘 A3 的时间复杂度为 w1×h1×n1 × w×h×n。

### 回答3：
根据题目描述，我们可以将张量X按照模态1乘A1，按模态2乘A2，按模态3乘A3进行乘积运算。

首先，我们需要明确张量X的维度，假设其维度为(w, h, n)。

对于模态1乘A1，我们需要对X在模态1的维度上进行乘积操作，即对w维度进行乘法，得到的结果的维度为(h, n)。假设运算时间复杂度为O(W1)。

对于模态2乘A2，我们需要对上一步得到的结果在模态2的维度上进行乘积操作，即对h维度进行乘法，得到的结果的维度为(n)。假设运算时间复杂度为O(H2)。

对于模态3乘A3，我们需要对上一步得到的结果在模态3的维度上进行乘积操作，即对n维度进行乘法，得到的结果的维度为(1)。假设运算时间复杂度为O(N3)。

综上所述，将张量X按模态1乘A1按模态2乘A2模态3乘A3的时间复杂度为O(W1 * H2 * N3)。

需要注意的是，这里的时间复杂度仅考虑了乘积操作的时间复杂度，而未考虑获取张量X和矩阵A的时间复杂度。在实际应用中，还需要综合考虑数据读取和计算的时间复杂度，才能得出更准确的时间复杂度分析。