反转单个单词并揭示直方图的秘密

引言

在算法和数据结构中有两个引人入胜的问题因其操作的多样性和复杂性而脱颖而出：字符串中单个单词的变形以及直方图中一个大块状区域的确定。

转换单个单词

打破言语保密

将单词串中的单个单词转换的任务起初可能听起来微不足道。然而，这个隐藏着言语相似性之间深层联系的算法挑战，以一句陈述作为输入，并处理每个单词，同时保持陈述中单词的顺序。

考虑表达式“algorithmic phenomenon”（算法现象）。算法必须反转每个单词，执行“cimhtiroglA srednoW”（算法现象）。实现这一点需要一种周密的、平衡效率和简洁性的方法。

算法结果

1. 分词

第一步是将输入字符串分解成单个单词。这个过程称为分词，包括根据空格分隔单词。

2. 同义词

分词后，每个单词单独反转。这可以通过类似于切片或递归交换字符的方式完成。

3. 重组

最终，转换后的单词被重新组合成修改后的陈述。

Python 实现

让我们更深入地探讨这个算法的 Python 实现。前面的代码片段很好地捕捉了结果的本质。它将输入句子分解成单词，转换每个单词，然后将它们重新组合以重建转换后的句子。

直方图中最大矩形区域

建筑灵感已揭示。

从语言学转向架构，直方图中最大块状区域的改变问题提出了一个引人入胜的挑战。想象一个由数组表示的直方图，其中每个元素定义了条形的高度。其思想是通过考虑条形的各种组合作为结构块来找到直方图中最大的块状区域。

算法结果

1. 基于栈的方法

解决此问题的一种入门方法是使用栈来检查按升序排列的树形指示器的条形高度。

2. 重复检查：算法再次遍历直方图，并且可以忽视栈来跟踪已添加的条形高度。然而，它计算由栈中弹出的指示器处的条形所形成的面积，作为当前指示器的一个范围。

如果它遇到一个比栈顶指示器处的条形更低的条形，

3. 优雅的审查：通过重复这个过程，算法搜索所有可能的三角形区域，并从中识别出最大的。

算法魔法起作用。

让我们用一段 Python 代码来畅想这个算法的魔力。

找出给定直方图中可能的最大矩形面积，其中最大矩形可以由高度由数组给出的连续条形组成。为简单起见，假设所有条形的宽度相同，并且宽度为 1 个单位。

示例

输入：直方图 = {6, 2, 5, 4, 5, 1, 6}

输出 12

输入：直方图 = {3, 5, 1, 7, 5, 9}

输出 15

直方图中最大矩形的面积。按照给定的步骤解决问题。

1. 创建一个空栈。
2. 从第一个条形开始，对每个条形 [i] 执行以下操作，其中 'i' 从 0 到 n-1。
3. 如果栈为空或 hist[i] 大于栈顶的条形，则将 'i' 推入栈以创建条形。
4. 如果当前条形小于栈顶条形，则继续弹出栈顶条形，直到栈顶条形的高度低于当前条形。
5. 令选定的条形为 [tp]。计算矩形的面积，将其高度视为 hist[tp]。
6. 对于 hist[tp]，'左索引'是栈中（tp 前面的）前一个元素，'右索引'是 'i'（当前索引）。
7. 当栈为空时，逐个弹出栈中的所有元素，并对每个弹出的元素执行步骤 (2.2 和 2.3)。

以下是上述技术的实现。

输出

上述代码的输出是

说明

提供的 Python 程序计算给定直方图中可以形成的最大的块状区域。直方图表示为列表，其中每个元素对应于条形的高度。目的是找到这些条形的操作可以形成的立方体的最大面积。

程序使用栈结构来正确确定最有利的位置。它遍历直方图中的每个条形，并使用条形指示器维护一个栈，按其高度的顺序入栈。栈使我们能够找出块状墙壁的容量。

算法逐个处理每个条形。然而，如果栈顶条形的高度大于或等于栈顶条形的高度（或如果栈为空），它会将当前条形的指示器推入栈。通过这个系统，当前条形可能会扩展当前矩形。然而，当当前条形比栈顶的条形短时，这个系统会从栈中弹出元素来计算可以用弹出的条形形成的矩形的最大面积，因为它是最短的条形。矩形的范围通过当前指示器和矩形左边界（或栈顶指示器）之间的差异来决定。

在遍历完所有条形后，该系统会检查栈中是否还有剩余的条形。对于每个剩余条形，它通过将其视为最短条形来计算面积。在生成过程中遇到的最大面积是最终结果。

在直方图 (6, 2, 5, 4, 5, 1, 6) 的手动示例中，计算并打印出最大立方体的位置，得出的结果是“最大立方体区域为 12。”

时间复杂度： O (N)。因为每个条形只入栈和出栈一次。

辅助空间：O(N)

通过查找下一个和前一个较小元素来计算直方图中最大矩形面积

要解决这个问题，请遵循以下思路。

为直方图的每个元素找到前一个和下一个较小元素，因为这将有助于计算当前元素是最小元素的子数组的长度。因此，我们可以使用该元素创建大小为 **（当前元素 * 子数组长度）** 的矩形。取所有此类矩形中的最大值。

按照给定的步骤解决问题。

• 首先，我们将创建两个数组 **left_smaller[]** 和 **right_smaller[]**，并分别用 -1 和 n 初始化它们。
• 对于每个元素，我们将在 left_smaller[] 和 right_smaller[] 数组中分别存储前一个较小元素和下一个较小元素的索引。
• 现在，对于每个元素，我们将通过将其作为 left_smaller[i] 和 right_smaller[i] 范围内的最小元素来计算面积，并将其乘以 left_smaller[i] 和 right_smaller[i] 之间的差值。
• 我们可以取步骤 3 中计算的所有面积的最大值来获得所需的 maximum area。

上述方法的实现如下。

输出

说明

提供的 Python 代码是查找直方图中最大矩形区域的另一项规则实现。与之前的实现类似，它使用一个栈来有效地组织直方图的条形。下面是对代码的解释：1. `get_Max_Area` 函数接受一个列表 `array` 作为输入，代表直方图，并返回其中可以形成的矩形的最大面积。2. 栈用单个元素 `-1` 初始化。它将按高度递增的顺序存储条形的索引。3. 两个数组 `left_smaller_area` 和 `right_smaller_area` 被初始化，用于分别存储每个条形左侧和右侧最近的较小元素的索引。4. 函数使用变量 `i` 遍历直方图中的每个条形。5. 当栈不为空且当前条形的高度小于栈顶条形的高度时，函数会更新栈顶条形的 `right_smaller_area` 并从栈中弹出该元素。6. 如果存在高度相同的连续条形，函数会通过更新当前条形的 `left_smaller_area` 来处理它，确保矩形宽度的正确计算。7. 当前条形的索引被推入栈，并且 `i` 递增。8. 处理完所有条形后，函数通过遍历每个条形来计算最大面积，将其视为潜在矩形的顶部，并使用 `right_smaller_area` 和 `left_smaller_area` 数组计算宽度。9. 然后返回计算出的最大面积。在直方图 `[6, 2, 5, 4, 5, 1, 6]` 的示例中，使用 `get_Max_Area` 函数计算矩形的最大面积，并打印结果。

时间复杂度：O(N)

辅助空间：O(N)

结论

在这项探索反转单个单词和查找直方图中最重要的矩形区域的研究中，我们揭示了这些算法奇迹所代表的美丽和复杂性。从语言学的对称性到建筑学的奇迹，这些艰巨的挑战让我们得以一窥算法问题解决的迷人世界。当我们继续我们在算法广阔领域的旅程时，我们发现每个问题都是一个等待解决的谜题，它揭示了计算思维的美丽和代码的艺术性。