Meta 只加高度成单调：单位成本贪心与方向比较

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练每次给一个高度加1，cost为总增加量、不允许降低；strict=True相邻严格，False允许相等。输出(cost,newList,orientation)，并列选increasing。
• 题目只给add on height/min operation，未给增量和严格性。一次可加任意高度且cost1时当前解不适用；实际操作合同仍列待核。

解题路线

1. 升序从左到右out[i]=max(original[i],out[i−1]+step)，严格step1、非严格0。每步选满足前缀的最小高度。
2. 逐项归纳：任意合法增加序列第1项至少original，后项至少自身original和前项+step；贪心各项不高于任意合法方案，因此总增加最小。
3. 降序从右到左同理。分别计算两方向cost取较小，不能只根据原首尾大小猜方向。
4. 保存两输出是为返回具体数组；仅求cost可左右分别维护previous与累计O(1)辅助，当前实现结果副本O(N)如实计。

手动走一遍

[3,1,2]严格升序[3,4,5]cost6，严格降序[4,3,2]cost3，选降序。[1,1]严格cost1、非严格0，重复值体现合同差异。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def raise_monotone(heights,strict=True):
    """Training one operation adds 1 to one height; no decreases.

    Return minimum total cost, resulting list, orientation; tie increasing.
    strict=False allows equal adjacent heights. Values are integer.
    """
    if any(not isinstance(h,int) for h in heights):raise ValueError('integer heights')
    step=1 if strict else 0
    def build(reverse):
        out=list(heights);indices=range(len(out)-1,-1,-1) if reverse else range(len(out));previous=None
        for i in indices:
            if previous is not None:out[i]=max(out[i],previous+step)
            previous=out[i]
        return sum(a-b for a,b in zip(out,heights)),out
    asc,a=build(False);desc,b=build(True)
    return (asc,a,'increasing') if asc<=desc else (desc,b,'decreasing')

复杂度

O(N)时间、当前O(N)数组空间，输出O(N)。不实际执行cost次单位操作，cost很大仍按元素数量扫描；整数位成本另计。

易错点与追问

容易失分的边界

• 任意增加算1操作与每单位算1混同，目标函数不同。
• 降序从左往右只增加后项不保证可行。

继续深挖

• 按修改元素数而非总增量计cost时，需要重新优化。
• 允许减少且绝对改动成本，当前单向贪心为什么不再成立？