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
|
# Задачи за стекове 12.10.22
## Задача първа
Имаме низ състоящ се от английски букви и символа \*. Всеки път когато видим \* трябва да премахнем символът отляво както и самата звезда.
Пример:
* aa\* -> "a"
* erase\*\*\*\*\* -> ""
* thi\*s i\*s exampl\*e -> "ths s exampe"
Задачата да се реализира за линейно време с линейна памет.
## Задача втора
* Вход: Низ състоящ се от отварящи и затварящи скоби.
* Изход: Дали скобите в този низ са балансирани
Примери:
* ((())) -> true
* ))() -> false
* )( -> false
* ()()(()) -> true
## Задача трета
Обратен полски запис наричаме запис, в който операторите "следват" (са след) числата. Примерно изразът 3 + 4 в обратна полска нотация е 3 4 +. Или изразът 1−2+3 би изглеждал 1 2 −3+. Обикновено първо са дадени числата а след това операциите които извършваме върху тях.
А как би изглеждал израза 1−(2+3). Тук първо трябва да извършим събирането и след това изваждането. Тоест израза се записва като 123+−. Предимството от тази нотация е, че нямаме нужда от скоби, което ускорява сметките. Нашата задача е да напишем функция, която приема валиден стринг в обратна полска нотация и връща пресметнатия резултат.
# Монотонни стекове
Монотонен стек наричаме стек, чиито елементи са монотонно растящи или намаляващи. Монотонните стекове имат приложения върхо много различни и интересни задачи върху масиви.
```cpp
void monotonicStackExample(const std::vector<int>& v) {
// Нека v = {4, 1, 2, 6, 7, 3}
// В стека можем да пазим стойности или индекси в зависимост от задачата.
// По името може да познаете какво пазим и какъв е типа на стека.
std::stack<int> minMonotonicValues;
for(int i = 0; i < v.size(); i++) {
while(!minMonotonicValues.empty() && minMonotonicValues.top() < v[i]) {
minMonotonicValues.pop();
}
minMonotonicValues.push(v[i]);
}
/*
В края на for цикъла при индекс i стека изглежда така:
(върха на стека е най - десния елемент)
i = 0 : [4]
i = 1 : [4, 1]
i = 2 : [4, 2]
i = 3 : [6]
i = 4 : [7]
i = 5 : [7, 3]
*/
}
```
Какво можем да забележим от този пример? Примерно, вярно е, че при i = k максимума на подмасива [0..k - 1] е на дъното на стека.
## Задача четвърта
Искаме да създадем статична структура от данни построена върху масив, която за константно време по индекс ни връща стойността на първия елемент намиращ се вляво от този индекс и имащ стойност по - голяма или равна от елемента на дадения индекс.
Пример:
> [1, 4, 3, 8, 12, 7]
* getMinLeft(0) -> -1 // няма по - голям елемент от 1 в негово ляво
* getMinLeft(2) -> 4 // 4 е първия елемент по - голям от arr[2] = 3
* getMinLeft(5) -> 12 // 12 е първия елемент по - голям от arr[5] = 7
## Обяснение на решението:
От тази задача можем да си направим извода, че точно преди да вкараме елемента в монотонния стек, върха на стека е първия елемент намиращ се вляво от този индекс и имащ стойност по - голяма или равна от елемента на дадения индекс.
Защо това е вярно?
Нека
$$arr = [a_1 \dots a_k \dots a_m \dots a_n]$$
и нека в цикъла i = m. Твърдя, че ако $a_k$ е първото по - голямо число от $a_m$ то ще бъде задължително на върха на стека след приключване на while цикъла.
Ако има други числа на върха на стека, то по предположение те са по - малки от $a_m$ и ще бъдат премахнати.
Ами ако $a_k$ не е в стека? Ако то не е в стека то някое по - голямо от него число, намиращо се между $a_k$ и $a_m$, го е премахнало. Тоест то не е първото по - голямо число намиращо се вляво.
## Бонус задачи
1. Да се сортира стек като използвате само един допълнителен стек.
2. Да се направи задачата със скобите, обаче този път функцията ни казва дали е възможно низът да стане балансиран след най - много едно изтриване на скоба.
Пример:
* )) -> false
* ()) -> true
* () -> true
* (()()() -> true
* ())) -> false
|
