【文末有福利】股票跨度——真实世界的算法

数学算法俱乐部

共 14231字，需浏览 29分钟

· 2020-08-18

数学算法俱乐部

日期：2020年08月15日

正文共：12997字10图

预计阅读时间：33分钟

来源：《真实世界的算法：初学者指南》

设想你可以获得一只股票的每日报价。也就是说，你得到一个数值序列，每个数表示一只给定股票在某天的收盘价。这些收盘价已按时间顺序排列好。股票市场关闭的日子没有对应的报价。

一只股票的价格在某天的跨度（span）是指这一天之前连续多少天股票价格低于或等于这天的价格。于是股票跨度问题（Stock Span Problem）定义为，给定一只股票的每日报价序列，对序列中每一天求出股票的跨度。例如，考虑图1-1。我们的数据从第0天开始，第6天的跨度为5天，第5天的跨度为4天，第4天的跨度为1天。

在现实中，股票每日报价序列可能包含数千天的数据，而我们可能希望对很多不同的序列计算跨度，每个序列描述了一只不同的股票的价格演变。因此我们希望使用计算机求解此问题。

对于很多用计算机来求解的问题，通常都存在多种求解方法，其中一些方法比另外一些更好。这里，“更好”这个词自身并没有什么实际意义。当我们说更好时，实际是说某些方面更好。可能是速度方面、内存方面或是影响时间和空间等资源的其他方面。我们会对此进行更多的讨论，但重要的是从一开始就要记住这一点，因为问题的一个解可能很简单但按照我们设置的一些约束或标准并不是最优的。

假定你正在计算序列中第m天的股票跨度，一种方法是回退一天，这样就处于第m-1天。如果第m-1天的价格大于第m天的价格，你就知道了第m天的股票跨度仅为1天。但如果第m-1天的价格小于或等于第m天的价格，则第m天的股票跨度至少为2天，也可能更大，取决于更早的股票价格是多少。因此我们继续检查第m-2天的价格。如果价格不大于第m天的价格，则检查再前一天，依此类推。最终可能发生两种情况：第一种情况是检查完所有日期（即到达了序列的起点），也就是第m天之前的所有股票价格都小于或等于第m天，于是跨度恰为m天；第二种情况是检查到第k（k＜m）天时，发现股票价格高于第m天，则跨度为m-k天。

如果序列包含n天的数据，则为了求解跨度问题需要重复上述过程n次，每次计算出一天的跨度。你可以在图1-1的例子上仔细验证此过程的正确性。

现在还有一个问题，上面对求解过程的描述并不是一种非常好的方式。在这个世界上，散文是交流几乎所有事情的极好方式，但提供给计算机的过程除外，因为在描述提供给计算机的东西时，必须十分精确。

如果我们的描述足够精确，计算机能够理解我们的过程，就意味着我们已经创建了一个程序（program）。但用计算机程序来描述一个过程可能又并非易于人类理解的最佳方式，因为你必须告诉计算机要做的所有细节，而且是以计算机的工作方式告诉它，而这些不一定与问题的解相关。一个描述如果足够详细、可被计算机理解，对于人类来说可能就过于详细而难于理解了。

因此我们可以做一下权衡，通过某种比简单文本更精确的结构化语言来描述求解过程，而且人类理解它也没有什么困难。这种结构化语言不一定能被计算机直接执行，但可以简单地转换为真正的计算机程序。

1.1算法

在求解股票跨度问题之前，你最好熟悉一个重要的术语。算法（algorithm）就是一个过程，是一种特殊的过程。它必须描述为一个有限步骤序列，且必须在有限时间内结束。每个步骤必须是良好定义的，达到人类可用一支笔和一张纸执行它的程度。算法基于我们提供给它的输入做一些事情，并生成反映其所做工作的一些输出。算法1-1实现了我们前面描述的过程。

算法1-1展示了如何描述算法。我们并不使用某种计算机语言，因为那样会迫使我们处理与算法逻辑无关的实现细节，我们使用的是某种伪代码（pseudocode）形式。伪代码是一种介于真正的程序代码和非形式化描述之间的形式。它使用一种结构化格式，并采用一组具有特定含义的词汇。但是，伪代码不是真正的计算机代码。它并不是为了被计算机执行，而是易于被人类理解。顺便提一下，程序也应能被人类理解，但并非所有程序都是如此——有很多正在运行的计算机程序写得很糟糕，难以理解。

每个算法都有一个名字，接受一些输入，并生成一些输出。在本书中，算法的名字将采用骆驼拼写法（CamelCase），输入会写在括号中，输出用一个→指示。接下来的几行将会对算法的输入和输出进行描述。可以用算法的名字紧接放在括号中的输入来调用（call）算法。一旦算法编写好，就可以将其作为一个黑盒来处理，可以给它一些输入，黑盒则会返回算法的输出。当用一种程序设计语言实现一个算法时，它就是一个具名的计算机代码片段——函数（function）。在一个计算机程序中，我们调用实现算法的函数。

某些算法不生成输出，当然也就不会显式返回结果。取而代之的是，它们的行为影响上下文的某部分。例如，我们可能提供给算法一个空间，供其写入结果。在此情况下，在传统意义上算法并非返回输出结果，但无论如何算法是有输出的，即它影响上下文发生的变化。某些程序设计语言会区分显式返回结果的具名程序代码片段——称为函数（function），以及不返回结果但可能有其他副作用的具名程序代码片段——称为过程（procedure）。这种差异来源于数学，数学上的函数是必须返回值的。对我们来说，当一个算法编码为实际程序时，既可以是一个函数也可以是一个过程。

我们的伪代码中使用一些用粗体表示的关键字，如果你对计算机和程序设计语言的工作方式有所了解，这些关键字的含义就是不言自明的了。我们使用字符←表示赋值，用等号（=）表示相等比较。我们采用常用的五个符号（+，-，/，×，·）表示四种数学运算，后两个符号都表示乘法，这两个符号我们都会使用，基于美学考虑进行选择。我们将不会使用任何关键字或符号对伪代码分块，分块是通过缩进来表示的。

在这个算法中，我们使用了数组（array）。数组是一种保存数据的结构，它允许我们按特定方式操纵其中的数据。我们保存数据并允许在其保存的数据上执行特定操作的结构称为数据结构（data structure）。因此数组是一种数据结构。

数组之于计算机，就像对象序列之于人类。数组是元素的有序序列，这些元素存储在计算机内存中。为了获得保存元素所需的空间并创建一个保存n个元素的数组，可调用算法1-1第1行中的CreateArray算法。如果你熟悉数组，可能就会奇怪创建数组怎么还需要一个算法。但实际情况的确如此。为了获得保存数据的一块内存，你必须至少在计算机中搜索可用内存并标记它为数组所用。CreateArray(n)调用做了所需的一切，它返回一个可容纳n个元素的数组，初始时其中没有元素，只有保存元素所需的空间。算法负责调用CreateArray(n)来将实际数据填充到数组中。

对数组A，我们用A[i]表示其第i个元素，访问该元素也是用该符号。一个元素在数组中的位置，如A[i]中的i，被称为索引（index）。一个n个元素的数组A包含元素A[0]，A[1]，…，A[n-1]。这可能令你吃惊，因为其首元素是第0个，而尾元素是第n-1个，可能你的预期是第1个和第n个。但是，大多数计算机语言中的数组都是如此，你最好现在就熟悉这种机制。这非常常见，当遍历一个大小为n的数组时，我们是从位置0遍历到位置n-1。在我们的算法中，当我们说某个对象的取值是从数x到数y（假定x小于y）时，意思是从x到y（但不包含）的所有值，参见算法第2行。

我们假定无论i的值是什么，访问第i个元素都花费相同的时间。因此访问A[0]与访问A[n-1]需要相同的时间。这是数组的一个非常重要的特性：对元素的访问是一致的，都花费常量时间。当我们通过索引访问数组元素时，数组不需要搜索此元素。

关于算法描述中的符号表示，我们用小写字母表示算法中的变量。但当变量表示一个数据结构时，我们会使用大写字母来令其突出，如数组A。但这并非必要。当我们希望给变量起一个包含很多单词的名字时，我们会使用下划线（_），如a_connector。这是必要的，因为计算机不理解由一组空格分隔的单词构成单个变量名的方式。

算法1-1使用数组保存数值。数组可以保存任何类型的项，在我们的伪代码中每个数组只能保存单一类型的项。大多数程序设计语言中也都是如此。例如，可以创建十进制数数组、分数数组、表示人的项的数组以及另一个表示地址的项的数组，但不可以创建一个既包含十进制数又包含表示人的项的数组。至于“表示人的项”会是什么，由编程所使用的语言所决定。所有程序设计语言都提供表示有意义的东西的方法。

一种特别有用的数组是字符数组。一个字符数组表示一个字符串（string），即一个字母序列、一个数序列、一个单词序列、一个句子序列等。与所有数组一样，我们可以用索引单独引用数组中的单个字符。如果我们有一个字符串s=“Hello，World”，则s[0]为字母“H”而s[11]为字母“d”。

总结一下，数组就是一个保存相同类型项的序列的数据结构。数组支持两种操作：

• CreateArray(n)创建一个能保存n个元素的数组。数组未初始化，即它不保存任何实际元素，但保存元素所需的空间已预留，可用来保存元素。

• 正如我们已经看到的，对一个数组A，A[i]访问其第i个元素，而且访问数组中任何元素都花费相同时间。若i＜0，则试图访问A[i]会产生错误。

我们回到算法1-1。如前所述，算法第2～10行是一个循环，即一个反复执行的代码块。如果我们有n天的报价的话，循环执行n次，每次计算一个跨度。变量i表示我们正在计算跨度的当前这一天。初始时，处于第0天这一最早的时间点。每次执行第2行代码时，就会推进循环到第1，2，…，n-1天。

我们使用变量（variable）k指示当前跨度的长度——在我们的伪代码中，变量就是一个引用某些数据的名字，那些数据的内容，或者更精确地说，变量的值（value），在算法执行的过程中是可以改变的，变量这个术语因而得名。当我们开始计算一个跨度时，k的值总是1，我们是在第3行设置这个初值的。我们还使用了一个指示变量（indicator variable）span_end。指示变量取值TRUE或FALSE，指出某事成立或不成立。当我们到达一个跨度的末端时，变量span_end的值将为真。

在开始计算每个跨度时，span_end为假，如第4行所示。第5～9行的内层循环计算跨度的长度。第5行告诉我们，只要跨度还未结束，就回退尽可能长的时间。我们能回退多远由条件i-k≥0决定：回退到索引i-k指示的这一天检查跨度是否结束，而索引不能为0，因为0对应第1天。第6行检查跨度是否结束。如果跨度未结束，则在第7行增加其长度。否则，我们注意到，第9行设置跨度结束，从而循环会在回到第5行后终止。第2～10行的外层循环在第10行结束一次循环时，我们在此将k的值保存到数组spans的正确位置。在退出循环后的第11行，我们返回spans，它保存着算法的结果。

注意，初始时我们设定i=0和k=1。这意味着在最早的时刻第5行的条件必定为假。这是理所应当的，因为第0天的跨度只能为1。

此时此刻，记住我们曾说过的关于算法、笔和纸的内容。理解一个算法的最好方法就是去手动执行它。在任何时候如果一个算法看起来有些复杂，或者你不确定是否已完全理解它，就用纸和笔写下执行它求解某个例子的过程。这种方法会节省你很多时间，虽然它看起来有点老套。如果对算法1-1还有不明确的地方，马上尝试这种方法，当算法已完全清晰后再回到这里。

1.2运行时间和复杂度

算法1-1给出了股票跨度问题的一种解决方案，但我们可以做得更好。在这里，更好的意思是可以做得更快。当讨论算法的速度时，实际上讨论的是算法执行的步骤数。不管计算机变得多么快，即使计算步骤的执行越来越快，步骤数也是保持不变的，因此用算法所需的步骤数来评价算法的性能就是很合理的了。我们称步骤数为算法的运行时间（running time），它是一个纯数，不以任何时间单位来度量。使用时间单位会令运行时间的任何评价都与特定的计算机模型关联，从而降低其实用性。

我们来分析计算n只股票报价的跨度花费多长时间。算法由开始于第2行的循环构成，循环会执行n次，每次计算一个报价。然后是从第5行开始的内层循环，外层循环每次会执行此内层循环来计算对应股票报价的跨度。对每个报价，内层循环会将它与之前的所有报价进行比较。在最坏情况下，如果当前报价是最高的，则会检查之前所有的报价。如果第k个报价是之前所有报价中最高的，则内层循环会执行k次。因此，最坏情况下，即报价是降序排列的情况下，第6～7行会执行这么多次：

如果你觉得等式不是那么清晰，可以将1，2，…，n这些数都累加两次，这样就能容易地看出结果的确如此：

由于第6～7行是算法运行最多次的步骤，因此n(n-1)/2是算法最坏情况下的运行时间。

当我们讨论算法的运行时间时，真正感兴趣的实际上是输入数据很大（在我们的例子中，是数n很大）时的运行时间。这就是算法的渐近（asymptotic）运行时间，如此命名的原因是它刻画的是输入数据无限增大时算法的行为。为了描述渐近运行时间，我们使用一些特殊符号。对任意函数f(n)，如果n大于某个初始正值时函数f(n)小于或等于另一个函数g(n)（用某个正的常数c缩放，即cg(n)），我们就称O(f(n))=g(n)。更精确地，如果存在正常数c和n0使得0≤f(n)≤cg(n)对所有n≥n0成立，则我们称O(f(n))=g(n)。

符号O(f(n))被称为“大O符号”。记住，我们感兴趣的是大规模的输入，因为那是会节省最多时间的情况。看一下图1-2，其中我们绘制了两个函数f1(n)=20n+1000和f2(n)=n2。对较小的n，f1(n)的值更大，但情况很快就发生了巨大变化，n2的增长速度要快得多。

大O符号令我们可以简化复杂度描述中的函数。如果我们有一个像f(n)=3n3+5n2+2n+

1 000这样的函数，则可以简化表示为O(f(n))=n3。为什么可以这样？因为我们总是可以找到一个值c使得0≤f(n)≤cn3。一般而言，当我们有一个包含多项的函数时，其最大项会很快主导函数的增长，因此可以去掉最小的那些项，使用大O符号。因此O(a1nk+a2nk-1 +…+akn+b)=O(nk)。

这种描述算法运行时间的方式通常被称为算法的计算复杂度（computational complexity），或简称为复杂度（complexity）。我们研究算法运行时间时使用简化形式的函数，而研究表明，大多数算法的运行时间的确可以用少数简化函数之一描述。这意味着算法的复杂度通常可被归为少数常见类别之一。

首先是常量函数（constant function）f(n)=c。这就意味着无论n的值是什么，函数总是具有相同的值c。除非c的值高得离谱，否则这是我们希望一个算法能达到的最佳复杂度。用大O符号表示的话，根据定义，我们有正常数c和n0使得0≤f(n)≤cg(n)=c·1。实际上，c就是函数的常数值，而n0=1。因此，O(c)=O(1)。如果算法有这样的行为，我们称其为常量时间算法（constant time algorithm）。这实际上是用词不当，因为常量时间并不意味着无论给算法什么输入它都会花相同的时间。其准确含义是算法运行时间的上界与其输入无关。例如，一个简单的算法实现x＞0时将y的值加到x的值上，它就不总是花费相同的运行时间：若x＞0，它执行一次加法，否则什么也不做。但其上界是常数，即加法花费的时间，因此它应归入O(1)类。遗憾的是，常量时间的算法并不多。最常见的常量时间的操作是访问数组中的元素，其花费的时间是常数，不依赖于我们要访问的元素的索引。如我们已见到的，在一个包含n个元素的数组A中，访问A[0]和访问A[n-1]花费相同的时间。

在常量时间算法之后，就是对数时间（logarithmic time）算法了。对数函数或称对数（logarithm）为loga(n)，其定义是为了得到n而对a施加的幂次：若y=loga(n)，则n=ay。数a称为对数的底（base of the logarithm）。从对数的定义可知x=alogax，这表明对数是指数的逆。实际上，log327=3，而33=27。若a=10，即对数以10为底，则可简写为y=log(n)。在计算机中我们经常遇到以2为底的对数（base two logarithm），称为二进制对数，因此我们使用一个特殊的符号lg(n)=log2(n)来表示这种对数。这不同于所谓的自然对数（natural logarithm），即以e≈2.718 28为底的对数。自然对数也有其特殊符号表示：ln(n)=loge(n)。

数e有时也被称为欧拉数，因18世纪瑞士数学家莱昂哈德·欧拉而得名，它出现在很多不同领域中。它是n趋向于无穷时表达式(1+1/n)n的极限。虽然得名于欧拉，但它实际上是另一位生活在17世纪的瑞士数学家雅各比·伯努利发现的，伯努利当时正尝试提出一个计算连续利息的公式。

设想你将d美元存入银行，银行给你的利率是R%。如果利息是每年计算一次，则一年之后你的存款将增长到d+d(R/100)。设r=R/100，则你的存款是d(1+r)。你可以验证一下，如果R=50，r=1/2，你的存款将增长到1.5×d。如果利息每年计算两次，则每六个月的利率为r/2。六个月后你的存款为d(1+r/2)。再经过六个月，在年底的时候，你的存款为d(1+r/2)(1+r/2)=d(1+r/2)2。如果每年施行利息（或用专业术语说，复利计算）n次，则到年底你的存款变为d(1+r/n)n。对R=100%这样一个高利率，有r=1。如果按连续复利收益计算，即采用更小的时间间隔，n趋向于无穷的话，则当d=1时，到年底你的存款将增长到d(1+r/n)n=e。关于e的介绍就到这里。

对数的一个基本性质是不同底的对数只差一个常数系数，这是因为loga(n)=logb(n)/logb(a)。例如，lg(n)=log10(n)/log10(2)。因此，虽然更特殊的O(lg(n))用得更多一些，但是我们将所有对数函数捆绑在相同的复杂度类别下，通常将其表示为O(log(n))。O(lg(n))复杂度的算法通常是反复将问题一分为二的算法，因为如果你反复将某个东西一分为二，本质上就是在对它应用对数函数。重要的对数时间算法都与搜索相关：最快的搜索算法的运行时间是以2为底的对数。

比对数时间算法更耗时的就是线性时间算法（linear time algorithm）了，其运行时间为f(n)=n，即时间与其输入成比例。对这些算法，复杂度描述为O(n)。这样的算法可能是扫描其整个输入来寻找答案。例如，如果我们搜索一个未经任何方式排序的项的随机集合，则可能不得不遍历所有项来找到我们想要的东西。因此，进行这样一次搜索的运行时间是线性的。

比线性时间更慢的是对数线性时间算法（loglinear time algorithm），其中f(n)=nlog(n)，因此复杂度描述为O(nlog(n))。虽然实际算法中以2为底最为常见，但是对数依旧可以是任意的底。这些算法某种程度上是线性时间算法和对数时间算法的组合，可能包含反复划分问题的步骤及对划分开的每个部分应用线性时间算法的步骤。好的排序算法具有对数线性时间复杂度。

如我们已经看到的，当描述算法运行时间的函数是一个多项式f(n)=a1nk+a2nk-1+…+akn+b时，我们有复杂度O(nk)，算法称为多项式时间算法（polynomial time algorithm）。很多算法是多项式时间的。一个很重要的子类别是O(n2)时间的算法，我们称其为平方时间算法（quadratic time algorithm）。一些效率不高的排序算法就是平方时间的，将两个n位数字的数相乘的标准算法也是平方时间的——注意，实际上更高效的乘法算法是存在的，在需要高性能算术计算的应用中我们就会使用这些高效方法。

比多项式时间算法更慢的是指数时间算法（exponential time algorithm），其中f(n)=cn，c是一个常数值，因此大O符号表示为O(cn)。务必注意nc和cn的差别。虽然只是交换了n和指数的位置，但导致了函数间的巨大差异。如前所述，幂运算是对数函数的逆，它简单地取一个常数的变量次幂。要小心：幂运算是cn。指数函数（exponential function）是c=e时的特例，即f(n)=en，其中e是前面提到的欧拉数。指数时间产生的情况是，我们需要处理一个输入规模为n的问题，其中每个输入都会取c个不同的值，而我们必须尝试所有可能情况：对第一个输入有c种取值，对其中每个值，都要考虑第二个输入的c个值，共c×c=c2种情况；对这c2种情况中的每一种，都要考虑第三个输入的c个可能值，使得总情况数变为c2×c=c3；依此类推，直到最后一个输入，总情况数变为cn。

比指数时间算法还慢的是阶乘时间算法（factorial time algorithm）O(n!)，其中阶乘数定义为n!=1×2×…×n，退化情况为0!=1。当求解一个问题，需要尝试输入的所有可能排列（permutation）时，就会产生阶乘时间。对于一个值的序列，它的一个排列就是值的顺序的一个不同的安排。例如，如果有值[1，2，3]，则有如下排列：[1，2，3]，[1，3，2]，[2，1，3]，[2，3，1]，[3，1，2]和[3，2，1]。在第一个位置上有n个可能的值。由于我们已经用了一个值，因此在第二个位置上有n-1个可能值，前两个位置的不同排列共有n×(n-1)种。对剩余位置我们像这样继续下去，直到在最后一个位置上只有一个可能值。因此，总共有n×(n-1)×…×1=n!种情况。阶乘数也出现在洗牌中：一副扑克牌可能的洗牌数有52!种，这是一个天文数字。

经验法则是，一个好的算法其时间复杂度最大是多项式的，因此我们的挑战通常是寻找具有这样性能的算法。遗憾的是，对于一大类重要的问题，我们知道它们没有多项式时间算法！看一下表1-1，你应该认识到，如果对一个问题我们只有一个运行时间为O(2n)的算法，则除了对一些简单问题或很小规模的输入外，该算法几乎毫无价值。你可以通过图1-3验证这一点：在最后一行，对较小的n值，O(2n)和O(n!)开始飞涨。

在图1-3中，显示了针对几个函数绘制的曲线，而实际上我们在研究算法时n都是自然数，因此我们预期看到的是显示点而非线的散点图。对数、线性、对数线性和多项式函数当然都是直接对实数定义的，因此使用正常的函数定义绘制它们的曲线没有什么问题。幂运算的解释通常是针对整数的，但有理数指数的幂也是可能的，因为xa/b=(xa)1/b= 。于是实数指数的幂定义为bx=(elnb)x=exlnb。至于阶乘，用一些更高等的数学知识，已证明可对所有实数定义（负阶乘被当作无穷）。因此我们将复杂度函数绘制为曲线是合理的。

为避免你认为O(2n)或O(n!)的复杂度在实际中很少出现，请考虑著名的旅行商问题。在这个问题中，一个旅行商必须访问一些城市，每个城市只能访问一次。每个城市都直接连接着其他每个城市（可能旅行商是乘飞机旅行）。难点在于旅行商在完成这一目标的同时还要经过的公里数尽量少。一个直接的求解方案是尝试这些城市所有可能的排列。对于n个城市，复杂度为O(n!)。存在一个求解此问题的更好算法，复杂度为O(n22n)——只好一点点，在实际应用中没有很大差别。那么，我们该如何解决此问题（以及其他类似问题）呢？已证明，虽然我们可能不知道一个能给我们精确答案的好算法，但我们可能知道能给出近似结果的好算法。

大O符号给出了一个算法的性能的上界（upper bound）。与之相反的是下界（lower bound），也就是说，我们知道其复杂度在一些初始值之后就永远不会好于某个函数。下界的符号表示是Ω(n)，称为big-Omega，精确的定义是，如果存在正常数c和n0，使得f(n)≥ cg(n)≥0对所有n≥n0成立，则我们称Ω(f(n))=g(n)。定义了大O和big-Omega之后，我们还可以定义同时有上界和下界的情况。这就是big-Theta，我们说Θ(f(n))=g(n)当且仅当O(f(n))=g(n)且Ω(f(n))=g(n)。于是我们知道算法运行时间的下界和上界是同一个函数，且用相同的常数缩放。你可以想象为算法的运行时间位于围绕该函数的一个带状区域中。

1.3使用栈求解股票跨度

现在我们回到股票跨度问题。我们已经找到了一个复杂度为O(n(n-1/2))的算法。根据我们之前的讨论，这等价于O(n2)。能做得更好吗？回到图1-1，注意到，当处于第6天时，我们不必与之前每一天进行比较直至第1天。因为我们已经遍历了每一天才来到第6天，所以已经“知道”第2，3，4，5天的报价小于或等于第6天。如果我们用某种方法保存这些信息，就不必进行所有这些比较，只需与第1天的报价进行比较即可。

这是一种通用的模式。设想你位于第k天。如果第k-1天的股票报价小于或等于第k天的股票报价，于是我们有quotes[k-1]≤quotes[k]或等价的quotes[k]≥quotes[k-1]，则算法接下来甚至没有再与第k-1天进行比较的必要了。为什么？考虑未来的第k+j天，如果其报价小于第k天的报价，即quotes[k+j]＜quotes[k]，则我们不必再将它与第k-1天进行比较，因为从k+j开始的跨度结束于k。如果第k+j天的报价大于第k天的报价，则我们已经知道必然有quotes[k+j]≥quotes[k-1]，因为quotes[k+j]≥quotes[k]且quotes[k]≥quotes[k-1]。因此每次当我们为计算某天的跨度而向后搜索跨度的末端时，就可丢弃所有报价小于或等于这天的那些天，而且在计算任何未来的跨度时都可排除丢弃的这些天。一般而言，在每一天，你只需与直接在你视线中的那些天进行比较。

下面的比喻可能会有助于理解：请看图1-4，设想你位于第6天对应的柱子的顶端，你向后平视，不要向下看，则只会看到第1天对应的柱子，而这也是需要与第6天比较股票价格的唯一一天。

这意味着在算法1-1第5行开始的内层循环，我们开始与之前的每一天进行比较是浪费时间的。我们可以使用某种机制，随手可得已建立最大跨度的范围，从而避免这种浪费。

为了实现这种机制，我们可以使用一种称为栈（stack）的特殊数据结构。栈是一种简单的数据结构，我们可以逐个向其中放入数据，也可以提取这些数据。每次我们取出的数据都是之前最后放入的。栈的工作机制像是餐馆里的一叠托盘，每个托盘都堆叠在其他托盘上面。我们只能取顶端的托盘，也只能新加托盘到顶端。由于最后加入的托盘最先被移出，因此我们称栈是一种后进先出（Last In First Out，LIFO）的数据结构。在图1-5中，可以看到在类似托盘操作的栈中添加和删除项的操作。

当我们讨论数据结构时，需要描述在数据结构上可以执行什么操作。对数组，我们看到了创建数组和访问元素两个操作。对栈，基于前面的描述，五种栈操作是：

• CreateStack()：创建一个空栈。

• Push(S，i)：将项i压入栈S的栈顶。

• Pop(S)：将栈S栈顶的项弹出，返回此项。如果栈空，此操作不被允许，我们得到一个错误。

• Top(S)：得到栈S栈顶项的值，但并不将其移出，栈保持不变。如果栈空，此操作不被允许，我们得到一个错误。

• Is Stack Empty(S)：若栈S空，返回TRUE，否则返回FALSE。

在实际中栈是有限的：在达到限制之前我们只能向其中压入一定数量的元素——毕竟一台计算机的内存有限。在栈的实际实现中，还有额外的操作来检查栈中元素的数目（其大小）以及栈是否满。这些操作与我们用伪代码描述的算法无关，因此不再对它们进行讨论。对我们将要讨论的其他数据结构中的相关操作也是如此。

如算法1-2所示，可以使用栈来实现前面提出的求解股票跨度问题的思路。与之前的算法一样，在算法开始的第1行我们创建了一个大小为n的空数组。由跨度定义，第1天的跨度为1，于是我们在第2行据此对spans[0]进行初始化。这一次我们使用一个栈来保存要比较的那些天。为此，我们在第3行创建了一个空栈。在算法开始我们有一个不起眼的事实：第1天的股票价格不会比它自身更低，因此在第4行我们将0即第1天的索引压入栈中。

第5～12行的循环处理随后的每一天。第6～7行的内层循环查看向后时间，寻找股票价格高于当前处理这天的最近一天。具体方法是，只要栈顶这天的股票价格小于或等于当前处理这天的价格（第6行），就从栈中弹出一项（第7行）。如果我们是在计算第i天跨度时由于耗尽栈中元素而退出内层循环（第8行），则之前每一天的股票价格都更低，因此跨度为i+1。我们在第9行将此值赋予spans[i]。否则（第10行），跨度即为第i天到栈顶那天，于是我们在第11行将两者的差值赋予spans[i]。在返回循环起点之前，我们将第i天压入栈顶。这样，在外层循环结束时，栈中保存的那些天的股票价格都不小于我们正在处理的这天的股票价格。这令我们在循环的下一步可以只与要紧的那些天进行比较，即高于我们视线的那些天，它们才是我们需要的。

算法第6行有一个值得我们注意的细节。如果S为空，则对Top(S)求值是一个错误。但由于条件表达式求值的一个重要性质——短路求值（short circuit evaluation），错误并不会发生。这条性质意味着：当我们对一个包含逻辑布尔运算符的表达式进行求值时，只要知道最终结果就立即停止对表达式的求值，而不必再对表达式的任何剩余部分求值。以表达式if x＞0 and y＞0为例，如果我们知道x≤0，则不管y的值如何，整个表达式都为假，完全没必要对表达式的第二部分进行求值。类似地，在表达式if x＞0 or y＞0中，如果我们知道x＞0，则没有必要对表达式的第二部分即包含y的部分进行求值，因为我们已经知道当第一部分为真时整个表达式即为真。表1-2显示了用and或or运算符的两部分布尔表达式的一般情况。阴影行表示表达式的结果不依赖于第二部分，因此一旦我们知道了第一部分的值就可以停止对表达式的求值。采用短路求值机制，当算法1-2中的IsStackEmpty(S)返回TRUE，也就是not IsStackEmpty(S)为假时，我们将不再试图对包含Top(S)的and右侧部分进行求值，因而避免了错误发生。

在图1-6中，你可以看到算法是如何工作的以及视线的比喻。在每个子图的右侧我们显示了每个循环步开始时栈的内容。我们还用填充柱指出了栈中有哪些天，而还未处理的天用虚线柱表示。我们正在计算跨度的当前这天用子图下方的黑色圈码表示。

在第一个子图中有i=1，我们必须将当前这天的股票价格与栈中那些天的股票价格进行比较，此时栈中只有第0天。第1天的价格比第0天高，这意味着从现在开始就不再需要与第1天之前的那些天进行比较了，我们的视线将止于此。因此在下一步循环中，i=2，栈中包含数1。第2天的价格比第1天低，这意味着如果第3天的价格低于第2天的价格，则始于第3天的任何跨度计算会终止于第2天，否则，如果第3天的价格不小于第2天的价格，就可能终止于第1天。但不会终止于第0天，因为第0天的价格小于第1天的价格。i=3和i=4也是类似情况。但当到达i=5时，我们意识到未来不再需要与第2，3，4天进行比较了。这些天位于第5天的阴影中。或者用视线的比喻说，我们的视野畅通无阻地一直回到第1天。两者之间的所有东西都可从栈中弹出，栈中将包含5和1，这样在i=6处，我们最多只需与这两天进行比较。如果某天的价格大于或等于第5天的价格，它当然也会大于第4，3，2天的价格，我们不能确定的只有它是否大于第1天的价格。当我们处理第6天时，栈中将包含数6和1。

算法1-2优于之前的算法吗？第5行开始的循环执行了n-1次。对于其中每一次（比如说第i次）循环，第6行开始的内层循环中的Pop操作执行pi次。这意味着Pop操作将总共执行p1+p2+…+pn-1次，外层循环每一步中执行pi次。我们不知道数pi是什么。但如果你密切关注算法，会看到每一天只会被压入栈中一次，第0天是在第4行，随后那些天是在第11行。于是，每一天在第7行从栈中弹出最多只有一次。因此，在算法的整个执行过程中，在外层循环的所有步骤中，第6行执行不会超过n次。换句话说，p1+p2+…+pn-1=n，这意味着整个算法是O(n)的。第7行是算法中执行次数最多的操作，因为它在内层循环中，而第5～12行的其余代码则不是。

继续分析可以看到，与只能得到最坏情况估计的算法1-1进行对比，我们对算法1-2的估计也是其性能的下界——算法不可能用少于n步完成这一任务，因为我们需要遍历n天。因此算法1-2的计算复杂度也是Ω(n)，于是它也是Θ(n)。

与我们将要遇到的所有其他数据结构一样，栈有很多用途。在计算机中LIFO行为是很常见的，因此从机器语言写成的底层程序到运行于超级计算机中的大型程序，你都能在其中发现栈。这就是数据结构存在的首要原因。数据结构不是别的什么，而是人类用计算机求解问题长年经验的精髓。事实一次又一次地证明，算法在用相似的方式来组织所处理的数据。人们将这些方法整理出来，使得当我们围绕一个问题寻找方法时，可直接找到它们，利用它们的功能来设计算法。

本文摘编自机械工业出版社华章公司出版的《真实世界的算法：初学者指南》

​【文末有福利】股票跨度——真实世界的算法

【文末有福利】股票跨度——真实世界的算法