元某人也元某人也

算法

算法与数据结构学习笔记，含 KMP 等经典算法。

本文目录

字符串

4、KMP算法（理论篇）

主要解决在一个文本串中是否出现过一个模式串的问题

（暴力解法思路：两个for循环遍历文本串和模式串，匹配不到就把匹配的位数向后移动一位直到匹配上为止，

时间复杂度为m*n

前缀表和后缀表

前缀：包含首字母不包含尾字母的所有子串

前缀：包含尾字母不包含首字母的所有子串

求最长相等的前后缀： 将一个个子串的最长相等前后缀记录下来对应到相应的子串数量位置组成前缀表

找到冲突的位置，再找前面的字串的最长相等前后缀，直接跳到对应的最长相等前后缀的长度，也就是节省了每次都要从头开始的遍历，前面和后面的长度是一样的，至于选取前缀和后缀的最长部分而不是随便找一段相同的是为了保证前面相等的部分是在字符串的头部开始的

5、KMP算法（代码篇）

next数组的不同实现方法

  1. 前缀表表示是当前位置前的子串对应的最长相等前后缀的数量，遇见冲突直接去找他的上一位对应的前缀表的数
  2. 前缀表统一向右移动一位最左边一位赋值-1，遇到冲突直接找当前位置对应的前缀表的数，回到-1是回到原点了

代码书写分为四步：

​ 两个指针：j指向前缀末尾位置（i之前的包括i的最长字串相等长度），i指向后缀末尾位置，

​ 是用了双指针的思想，一个指针从0开始，一个指针从1开始，假如两个位置不相等说明前后缀没有相等的地方就比如最简单的ab，当然假如是aa的话就是1了, 然后就是1了，其实是分开了就相当于是说比如我是到了aab的时候我的i是在b我的j在第一个a因为他回退是回退到n[j-1]，他俩不相等，我需要把i往后移一个此时的j会回退到0所以会把这个next[i]=j就为0，为啥可以只在相等的时候加一次就可以完成计数是因为可以把上一次的计数不回退，关于为啥会回退到上一个位置的最大相等长度，，我们要理解一下前缀和后缀的概念，包含当前位置的最大字串前缀是包含首字母，不包含尾字母，后缀是包含尾字母不包含首字母，回退到前一个位置的最大子串，回退到next[j-1]而非直接置 0，是为了复用之前的匹配结果，避免暴力匹配的重复比较，这也是 KMP 算法时间复杂度优化到O(n)的关键。

​ 求next[1]的操作就是，如果前后缀不同则回退，相同则更新next[1]值，这时[1]再求二，以此类推，直到更新完一遍（这个过程是在推演出前缀表）

  • 初始化：j=0;next[0]=0;（当只有一个字符的时候没有相等前后缀）i则是在for循环中进行的自增，不需要管他
  • 前后缀不相等：j要做的操作就是回退回退到next[j-1]，i操作是当前位置的next[i]=j.
  • 前后缀相等：需要的操作j++，
  • next[i]=j；
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/// <summary>
/// 获取模式串的Next数组（标准版本：存储最长相等前后缀长度）
/// </summary>
/// <param name="pattern">匹配的模式串</param>
/// <returns>int[]类型的Next数组</returns>
public static int[] GetNextArray(string pattern)
{
    // 判空处理
    if (string.IsNullOrEmpty(pattern)) return Array.Empty<int>();
    
    int len = pattern.Length;
    int[] next = new int[len];
    next[0] = 0; // 单个字符，无前后缀，固定为0
    
    int j = 0; // j：前缀末尾的指针，初始为0
    // i：后缀末尾的指针，从1开始遍历
    for (int i = 1; i < len; i++)
    {
        // 核心：前后缀不相等时，j回退到上一个匹配位置(next[j-1])
        while (j > 0 && pattern[i] != pattern[j])
        {
            j = next[j - 1];
        }
        
        // 前后缀相等时，j指针后移
        if (pattern[i] == pattern[j])
        {
            j++;
        }
        
        // 给当前位置赋值最长相等前后缀长度
        next[i] = j;
    }
    return next;
}

5、重复的子字符串

​ 任何一个由重复字串组成的字符串前半部分和后半部分一定会相等

​ 最长相等前后缀和重复子串的关系： 如果一个字符串是由重复的子字符串组成的，那么他的最小重复单位就是他的最长相等前后缀不包含的那一部分

暴力解法

先枚举出来所有的子串（有两个条件一个是只枚举前一半即可，字串长度是原字符串的约数）时间复杂度是n*2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {
    public bool RepeatedSubstringPattern(string s) {
        int n = s.Length;
        // 枚举所有可能的子串长度，只枚举前半段即可
        for (int len = 1; len <= n / 2; len++)
        {
            // 必须是约数，才能被均分
            if (n % len == 0)
            {
                string sub = s.Substring(0, len); // C#截取子串：Substring(起始索引, 截取长度)
                string temp = "";
                int repeatCount = n / len; // 需要重复的次数
                // 拼接子串
                for (int i = 0; i < repeatCount; i++)
                {
                    temp += sub;
                }
                // 判断拼接结果是否等于原字符串
                if (temp.Equals(s))
                {
                    return true;
                }
            }
        }
        return false;
    }
}

移动匹配法

​ 核心思路：字符串s能有字串构成，拼接两个s，t=s+s，在t去掉首位各一个字母的时候。新的字符串任然包含原来的字符串s举例：s=abab，t=abababab，去掉两边以后等于bababa，所得的结果可以有一个s那说明是由重复子串组成，这里的库函数Contains实现类似于KMP算法时间复杂度为n

1
2
3
4
5
6
7
8
9

public class Solution {
    public bool RepeatedSubstringPattern(string s) {
        string t = s + s;
        // 截取：从索引1开始，截取 总长度-2 个字符（等价于去掉首尾各1位）
        string subT = t.Substring(1, t.Length - 2);
        // 判断是否包含原字符串
        return subT.Contains(s);
    }
}

KMP算法

​ 取该数组的最长相等前后缀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Solution {
    public bool RepeatedSubstringPattern(string s) {
        int n = s.Length;
        if(n == 1) return false; // 边界：单个字符一定不满足
        
        // 1. 手动构建next数组
        int[] next = new int[n];
        int j = 0; // j表示「最长相等前后缀」的长度
        for(int i = 1; i < n; i++)
        {
            // 前后缀不相等，j回退到前一个最长相等前后缀的位置
            while(j > 0 && s[i] != s[j])
            {
                j = next[j - 1];
            }
            // 前后缀相等，最长长度+1
            if(s[i] == s[j])
            {
                j++;
            }
            next[i] = j;
        }

        // 2. 获取最后一位的next值，套用核心公式判断
        int lastNext = next[n - 1];
        return lastNext != 0 && n % (n - lastNext) == 0;
    }
}

栈和队列

1、用栈实现队列

​ 需要有两个栈来实现一个类似队列的方法，一个是入栈，一个是出栈

​ 需要注意的是每次都需要把所有的元素都从入栈全部转移到出栈中，否则会产生顺序上的错误

  • stack.Pop() → 有返回值、修改原栈：移除栈顶元素，返回被移除的元素
  • stack.Peek() → 有返回值、不修改原栈：仅获取栈顶元素，不移除，队列的「查看队首」就是靠它实现
  • stack.Push(val) → 无返回值、修改原栈：向栈顶添加元素
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

using System.Collections.Generic;

public class MyQueue
{
    // 输入栈：仅接收入队元素
    private Stack<int> _inStack;
    // 输出栈：仅提供出队/队首元素
    private Stack<int> _outStack;

    public MyQueue()
    {
        _inStack = new Stack<int>();
        _outStack = new Stack<int>();
    }

    /// <summary>
    /// 入队：将元素x推到队列的末尾
    /// </summary>
    public void Push(int x)
    {
        _inStack.Push(x);
    }

    /// <summary>
    /// 出队：移除并返回队列开头的元素
    /// </summary>
    public int Pop()
    {
        if (_outStack.Count == 0)
        {
            while (_inStack.Count > 0)
            {
                _outStack.Push(_inStack.Pop());
            }
        }
        return _outStack.Pop();
    }

    /// <summary>
    /// 获取队首元素：返回队列开头的元素（不移除）
    /// </summary>
    public int Peek()
    {
        if (_outStack.Count == 0)
        {
            while (_inStack.Count > 0)
            {
                _outStack.Push(_inStack.Pop());
            }
        }
        return _outStack.Peek();
    }

    /// <summary>
    /// 判断队列是否为空 - 逻辑直接写在return里，无任何额外封装
    /// </summary>
    public bool Empty()
    {
        return _inStack.Count == 0 && _outStack.Count == 0;
    }
}

2.用队列来实现栈

用两个队列来实现栈的大体思路

在入栈的时候直接装到一个队列里面，

在出栈实现的时候将前几个直接移动到第二个队列中将最后一个元素直接得到，再交换两个队列的元素，循环得到

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102

using System;
using System.Collections.Generic;

/// <summary>
/// 用两个队列实现的栈结构
/// </summary>
public class StackByTwoQueues<T>
{
    // 主队列，用于存储栈的元素
    private Queue<T> _queue1;
    // 辅助队列，用于出栈/取栈顶时临时存储元素
    private Queue<T> _queue2;

    /// <summary>
    /// 构造函数，初始化两个空队列
    /// </summary>
    public StackByTwoQueues()
    {
        _queue1 = new Queue<T>();
        _queue2 = new Queue<T>();
    }

    /// <summary>
    /// 入栈操作
    /// </summary>
    /// <param name="item">要入栈的元素</param>
    public void Push(T item)
    {
        // 入栈直接加入主队列
        _queue1.Enqueue(item);
    }

    /// <summary>
    /// 出栈操作（移除并返回栈顶元素）
    /// </summary>
    /// <returns>栈顶元素</returns>
    /// <exception cref="InvalidOperationException">栈为空时抛出异常</exception>
    public T Pop()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("栈为空，无法执行出栈操作");
        }

        // 将queue1中除最后一个元素外的所有元素移到queue2
        while (_queue1.Count > 1)
        {
            _queue2.Enqueue(_queue1.Dequeue());
        }

        // 取出queue1中最后一个元素（栈顶）
        T topItem = _queue1.Dequeue();

        // 交换两个队列的角色，让queue1始终作为主队列
        (_, _queue1) = (_queue1, _queue2);
        _queue2.Clear(); // 清空辅助队列，避免残留

        return topItem;
    }

    /// <summary>
    /// 获取栈顶元素（不移除）
    /// </summary>
    /// <returns>栈顶元素</returns>
    /// <exception cref="InvalidOperationException">栈为空时抛出异常</exception>
    public T Peek()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("栈为空，无法获取栈顶元素");
        }

        // 逻辑与Pop一致，但最后一个元素也要移到queue2
        while (_queue1.Count > 1)
        {
            _queue2.Enqueue(_queue1.Dequeue());
        }

        T topItem = _queue1.Dequeue();
        _queue2.Enqueue(topItem); // 把栈顶元素也加入辅助队列

        // 交换队列角色
        (_, _queue1) = (_queue1, _queue2);
        _queue2.Clear();

        return topItem;
    }

    /// <summary>
    /// 判断栈是否为空
    /// </summary>
    /// <returns>空返回true，否则返回false</returns>
    public bool IsEmpty()
    {
        return _queue1.Count == 0;
    }

    /// <summary>
    /// 获取栈的元素个数
    /// </summary>
    public int Count => _queue1.Count;
}

用一个队列实现栈的大体思路

入栈就正常的存入栈中

出栈的时候，将队列循环出列最后一个元素，同时加到高i队列的后面，只得到最后一个元素出栈

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108

using System;
using System.Collections.Generic;

/// <summary>
/// 用单个队列实现的栈结构
/// </summary>
/// <typeparam name="T">栈存储的元素类型</typeparam>
public class StackBySingleQueue<T>
{
    // 唯一的队列，用于模拟栈
    private Queue<T> _queue;

    /// <summary>
    /// 构造函数，初始化空队列
    /// </summary>
    public StackBySingleQueue()
    {
        _queue = new Queue<T>();
    }

    /// <summary>
    /// 入栈操作（核心逻辑：调整队列元素顺序）
    /// </summary>
    /// <param name="item">要入栈的元素</param>
    public void Push(T item)
    {
        // 1. 先把新元素加入队列尾部
        _queue.Enqueue(item);
        // 2. 记录当前队列中旧元素的个数（总个数-1，因为刚加了一个新元素）
        int oldElementCount = _queue.Count - 1;
        // 3. 把旧元素依次出队再入队，让新元素移到队列头部
        for (int i = 0; i < oldElementCount; i++)
        {
            T temp = _queue.Dequeue();
            _queue.Enqueue(temp);
        }
    }

    /// <summary>
    /// 出栈操作：移除并返回栈顶元素
    /// </summary>
    /// <returns>栈顶元素</returns>
    /// <exception cref="InvalidOperationException">栈为空时抛出异常</exception>
    public T Pop()
    {
        // 直接弹出队列头部（就是栈顶）
        return _queue.Dequeue();
    }

    /// <summary>
    /// 获取栈顶元素（不移除）
    /// </summary>
    /// <returns>栈顶元素</returns>
    /// <exception cref="InvalidOperationException">栈为空时抛出异常</exception>
    public T Peek()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("栈为空，无法获取栈顶元素");
        }
        // 直接取队列头部（就是栈顶）
        return _queue.Peek();
    }

    /// <summary>
    /// 判断栈是否为空
    /// </summary>
    /// <returns>空返回true，否则返回false</returns>
    public bool IsEmpty()
    {
        return _queue.Count == 0;
    }

    /// <summary>
    /// 获取栈的元素个数
    /// </summary>
    public int Count => _queue.Count;
}

// 测试代码
public class Program
{
    public static void Main()
    {
        StackBySingleQueue<int> stack = new StackBySingleQueue<int>();

        // 入栈：1 → 2 → 3
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);

        Console.WriteLine("栈顶元素：" + stack.Peek()); // 输出：3
        Console.WriteLine("栈元素个数：" + stack.Count); // 输出：3

        // 出栈
        Console.WriteLine("出栈元素：" + stack.Pop()); // 输出：3
        Console.WriteLine("出栈后栈顶：" + stack.Peek()); // 输出：2
        Console.WriteLine("出栈后元素个数：" + stack.Count); // 输出：2

        // 继续出栈
        stack.Pop();
        stack.Pop();
        Console.WriteLine("全部出栈后是否为空：" + stack.IsEmpty()); // 输出：True

        // 测试空栈出栈（会抛异常，可注释掉验证）
        // stack.Pop();
    }
}

3、有效括号（栈）

选择把右边填入栈中的原因：当判断到左边的时候直接将对应的右边填入，遇到右括号就开始遍历后面元素与栈中元素作比较，比较方便

对应到真实的有三种结构

  1. 左边多了（栈在遍历完后仍不为空）
  2. 右边多了（栈提前为空）
  3. 类型错误（栈中元素与当前遍历元素不匹配

做一个剪枝判断在判断是否有相应括号必须是偶数才可能是相互匹配的，如果是偶数直接返回（%2是否是0）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

using System;
using System.Collections.Generic;

public class Solution
{
	// 力扣题目核心方法：判断括号字符串是否有效
	public bool IsValid(string s)
	{
		// 边界条件：字符串长度为奇数，必无效（括号需成对出现）
		if (s.Length % 2 != 0)
			return false;

		Stack<char> bracketStack = new Stack<char>();
		//创建哈希表来将括号一一对应，方便压栈
		Dictionary<char,char> dict = new Dictionary<char, char>()
		{
			{'(',')' },
			{'{','}' },
			{'[',']' }
		};
		foreach (char c in s)
		{
			//这里直接采用检测是否包含对应的字母，如果包含直接压入栈中是不会破坏顺序的
			if(dict.ContainsKey(c))
			{
				bracketStack.Push(dict[c]);
			}
			else if(bracketStack.Count == 0||bracketStack.Peek()!=c)
			{
				return false;
			}
			else
				bracketStack.Pop();
		}
		
		// 最终判定：栈为空表示所有右括号都匹配成功，否则存在未匹配的右括号
		return bracketStack.Count == 0;
	}

	// 测试主方法（本地运行验证用，力扣提交时可删除）
	public static void Main(string[] args)
	{
		Solution solution = new Solution();
		// 测试用例
		Console.WriteLine(solution.IsValid("()"));       // 输出：True
		Console.WriteLine(solution.IsValid("()[]{}"));   // 输出：True
		Console.WriteLine(solution.IsValid("(]"));       // 输出：False
		Console.WriteLine(solution.IsValid("([)]"));     // 输出：False
		Console.WriteLine(solution.IsValid("{[]}"));     // 输出：True
		Console.WriteLine(solution.IsValid("{"));        // 输出：False
	}
}

4、消除字符串中相邻的重复项

这个题和上面的有效括号思路一致，相邻重复项在录入一个后，只需要在把另一个录入时与上一个位置的进行比较，相同则消除，不通则继续录入，避免了只消除一次的情况，最后将整个栈转换为数组，再反转，通过强制显式转换为字符串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

public class DuplicateRemover
{
	/// <summary>
	/// 核心方法：消除字符串中的相邻重复项（相邻相同字符成对消除）
	/// </summary>
	/// <param name="s">原始输入字符串</param>
	/// <returns>消除重复后的结果字符串</returns>
	public string RemoveAdjacentDuplicates(string s)
	{
		// 空值/空字符串直接返回，避免后续逻辑异常
		if (string.IsNullOrEmpty(s))
		{
			return string.Empty;
		}

		// 栈：存储未被消除的字符，核心数据结构
		Stack<char> charStack = new Stack<char>();

		// 遍历每个字符，执行核心消除逻辑
		foreach (char c in s)
		{
			// 栈非空且栈顶字符与当前字符相同 → 消除（弹出栈顶）
			if (charStack.Count > 0 && charStack.Peek() == c)
			{
				charStack.Pop();
			}
			// 栈空/栈顶字符不同 → 入栈暂存
			else
			{
				charStack.Push(c);
			}
		}

		// 栈中剩余字符是逆序的，需反转后转为字符串（栈：后进先出）
		char[] resultArr = charStack.ToArray();
		Array.Reverse(resultArr);
		//通过显式强转将字符类型转换为字符串
		return new string(resultArr);
	}
	static void Main(string[] args)
	{
		// 初始化工具类
		DuplicateRemover remover = new DuplicateRemover();

		// 定义测试用例：覆盖常规场景、连续重复、边界场景（空/单字符/全重复）
		string[] testCases = new string[]
		{
			"abbaca",    // 常规场景：消除后为 "ca"
            "aaaa",      // 连续重复：消除后为空
            "a",         // 单字符：无重复，返回自身
            "",          // 空字符串：返回空
            null,        // 空值：返回空
            "abba",      // 嵌套重复：消除后为空
            "abcde",     // 无重复：返回自身
            "aabbccddee" // 成对重复：消除后为空
        };

		// 遍历执行测试并输出结果
		Console.WriteLine("===== 相邻重复项消除测试结果 =====");
		foreach (var testStr in testCases)
		{
			string result = remover.RemoveAdjacentDuplicates(testStr);
			// 处理空值显示，让控制台输出更友好
			string inputDisplay = testStr ?? "null";
			Console.WriteLine($"输入：\"{inputDisplay}\" → 输出：\"{result}\"");
		}

		// 防止控制台直接退出（按任意键关闭）
		Console.WriteLine("\n按任意键退出程序...");
		Console.ReadKey();
	}
}

5、逆波兰表达式求值

前缀表达式（波兰式），后缀表达式（逆波兰式）是无括号的表达式表达法，核心优势是无需依赖括号和运算符优先级，即可完成计算，完全通过运算符与操作数的相对位置确定运算顺序，是编译器，计算器等程序处理表达式的核心基础。

栈的数据结构十分符合进行两个相邻字符之间的操作

三种表达式（等同于二叉树遍历中的前序遍历（根左右），中序遍历（左根右），后序遍历（左右根））

1. 中缀表达式（Infix Expression）

我们日常使用的表达式形式，运算符位于两个操作数中间，必须依赖括号和运算符优先级确定运算顺序，也是最符合人类阅读习惯的形式。

  • 示例：3 + 4 × 2、(3 + 4) × 2、a + b × c - (d + e)

2. 前缀表达式（Prefix Expression，波兰式）

运算符位于两个操作数前面 ，无括号、无优先级，按从右到左顺序扫描计算，运算符出现即对后续最近的两个操作数执行运算。

  • 格式：运算符 操作数1 操作数2
  • 示例：
    • 中缀3 + 4 × 2 → 前缀+ 3 × 4 2
    • 中缀(3 + 4) × 2 → 前缀× + 3 4 2

3. 后缀表达式（Postfix Expression，逆波兰式）

运算符位于两个操作数后面 ，无括号、无优先级，按从左到右顺序扫描计算，运算符出现即对前面最近的两个操作数执行运算（最常用，栈处理最便捷）。

  • 格式：操作数1 操作数2 运算符
  • 示例：
    • 中缀3 + 4 × 2 → 后缀3 4 2 × +
    • 中缀(3 + 4) × 2 → 后缀3 4 + 2 ×
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

using System;
using System.Collections.Generic;

public class Solution {
    public int EvalRPN(string[] tokens) {
        // 栈存储操作数，int类型适配题目数值范围
        Stack<int> numStack = new Stack<int>();
        foreach (string token in tokens) {
            // 是运算符：弹出两个操作数计算
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                int right = numStack.Pop(); // 先弹右操作数（关键：避免加减乘除顺序错误）
                int left = numStack.Pop();  // 后弹左操作数
                switch (token) {
                    case "+": numStack.Push(left + right); break;
                    case "-": numStack.Push(left - right); break;
                    case "*": numStack.Push(left * right); break;
                    case "/": 
                        // 题目要求：除法向零取整（C#默认向负无穷取整，需手动修正）
                        numStack.Push(left / right); 
                        break;
                }
            } else {
                // 是操作数：直接转int入栈
                numStack.Push(int.Parse(token));
            }
        }
        // 最终栈中唯一元素即为结果
        return numStack.Pop();
    }
}

6、滑动窗口最大值（单调队列的经典问题）

此时我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。

push（）

pop（）

front（）

不需要维护所有的元素，只需要保证队列中元素按照从大到小的顺序排列，比后一个元素小的直接移除

保持单调队列里单调递减，此时队列出口元素就是窗口里最大元素。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class myDequeue{
        private LinkedList<int> linkedList = new LinkedList<int>();
		//压入队列，压入的规则是按照输入的顺序来，如果前面有比当前位置小的，则移除前面较小的元素，有比较大的则直接保留
        public void Enqueue(int n){
            while(linkedList.Count > 0 && linkedList.Last.Value < n){
                linkedList.RemoveLast();
            }
            linkedList.AddLast(n);
        }

        public int Max(){
            return linkedList.First.Value;
        }

        public void Dequeue(int n){
            //因为我们只留下了最大的数，之后是从大到小单调递减的所以只有当最大值和移除元素相等的时候才需要移除，不相等的时候不采取任何措施，因为我们根被没有将他们加进来
            if(linkedList.First.Value == n){
                linkedList.RemoveFirst();
            }   
        }
    }

    myDequeue window = new myDequeue();
    List<int> res = new List<int>();

    public int[] MaxSlidingWindow(int[] nums, int k) {
        //先确定滑动窗口起始的位置
        for(int i = 0; i < k; i++){
            window.Enqueue(nums[i]);
        }
        //记录最大值
        res.Add(window.Max());
        for(int i = k; i < nums.Length; i++){
            //移除滑动窗口不包含位置的元素
            window.Dequeue(nums[i-k]);
            window.Enqueue(nums[i]);
            res.Add(window.Max());
        }

        return res.ToArray();
    }

7、前K个高频元素

给定一个数组，让你去求在这个数组中出现高频的前K个元素

仅用于交流学习，记录学习心得