<h2>简答,通解</h2>
<p>使用my <a href="https://stackoverflow.com/a/38337443/1916449">answer to the "Longest increasing subsequence" question</a>,这可以简单地实现为:</p>
<pre><code>def out_of_sequence(seq):
indices = set(longest_subsequence(seq, 'weak', key=lambda x: x[0], index=True))
return [e for i, e in enumerate(seq) if i not in indices]
</code></pre>
<h2>更长的答案,具体的解决方案</h2>
<p>基于<a href="https://codereview.stackexchange.com/q/10230/110989">question at Code Review</a>和<a href="https://stackoverflow.com/a/21718032/1916449">question about non-decreasing sequences</a>(因为这正是您所追求的),下面是您的问题的解决方案:</p>
^{pr2}$
<p>输出:</p>
<pre><code>('1929-03-12', 'name4')
('2023-07-01', 'name7')
('2015-02-15', 'namex')
('1980-12-23', 'name2')
</code></pre>
<hr/>
<p><code>key</code>参数(受<a href="https://docs.python.org/3.5/library/functions.html#sorted" rel="nofollow noreferrer">^{<cd2>}</a>内置函数的启发)指定一个由一个参数组成的函数,用于从每个列表元素中提取比较键。默认值是<code>None</code>,因此调用者可以方便地说“我想直接比较元素”。如果它被设置为<code>None</code>,我们使用<code>lambda x: x</code>作为<a href="https://en.wikipedia.org/wiki/Identity_function" rel="nofollow noreferrer">identity function</a>,因此在比较之前元素不会以任何方式更改。在</p>
<p>在您的例子中,您希望使用日期作为比较键,因此我们使用<a href="https://docs.python.org/3/library/operator.html#operator.itemgetter" rel="nofollow noreferrer">^{<cd6>}</a>作为<code>key</code>。并且<code>itemgetter(1)</code>将使用<code>key</code>的名称,请参见:</p>
^{4}$
<p>使用<code>itemgetter(k)</code>等同于<code>lambda x: x[k]</code>:</p>
<pre><code>>>> print(*map(lambda x: x[1], dates))
name1 nameg name5 nameh name4 name7 name0 nameh namex namew name2 namen named
</code></pre>
<p>将其与<code>map</code>一起使用相当于生成器表达式:</p>
<pre><code>>>> print(*(x[1] for x in dates))
name1 nameg name5 nameh name4 name7 name0 nameh namex namew name2 namen named
</code></pre>
<p>但是,如果我们使用类似的列表理解将序列传递给<code>out_of_sequence</code>,我们将得到与预期不同的结果:</p>
<pre><code>>>> print(*out_of_sequence([x[0] for x in dates]), sep='\n')
1929-03-12
2023-07-01
2015-02-15
1980-12-23
</code></pre>
<p>同样,如果我们直接比较日期名称对,我们会得到错误的结果(因为<code>'nameg'</code>比<code>'name5'</code>大):</p>
<pre><code>>>> print(*out_of_sequence(dates), sep='\n')
('2015-02-04', 'nameg')
('1929-03-12', 'name4')
('2023-07-01', 'name7')
('2015-02-15', 'namex')
('1980-12-23', 'name2')
</code></pre>
<p>因为我们要返回日期和名称,而且只想按日期排序,所以需要传递一个使用<code>key</code>参数提取日期的函数。在</p>
<p>另一种方法是去掉<code>key</code>,只写:</p>
<pre><code>j = bisect_right([seq[k][0] for k in lastoflength], seq[i][0])
</code></pre>
<p>但是由于这是stackoverflow,也许有一天另一个人会得到这个答案,并且需要一些其他的密钥提取,因此我决定在这里发布更一般的解决方案。在</p>