Diving at high altitudes does require a different set of tables or a computer that can adjust (manually or automatically) to the altitude. As the pressures are different, so are your NDL times at any given depth.
One example taken from the net:
Altitude-Adjusted Dive Depths
Left Column = Actual Depth of Dive in Feet -- Top Row = Altitude in Feet
Table Data = Effective Depth for Use in Standard Dive Table
Feet 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
10 10 11 11 12 12 12 13 13 14 15
20 21 21 22 23 24 25 26 27 28 29
30 31 32 33 35 36 37 39 40 42 44
40 41 43 45 46 48 50 52 54 56 58
50 52 54 56 58 60 62 65 67 70 73
60 62 64 67 69 72 75 78 81 84 87
70 72 75 78 81 84 87 91 94 98 102
80 83 86 89 92 96 100 103 108 112 116
90 93 97 100 104 108 112 116 121 126 131
100 103 107 111 116 120 124 129 134 140 145
110 114 118 122 127 132 137 142 148 153 160
120 124 129 134 139 144 149 155 161 167 174
130 135 140 145 150 156 162 168 175 181 189
Round upward to next 10 feet depth and next 1000 feet altitude.
Instructions: For the altitude of the dive, use your HIGHEST elevation for 24 hours after the dive. Round upward. (For example, if you dive at 6500 feet then drive over a mountain pass at 8900 feet, use 9000 feet as the dive altitude.) Find the appropriate altitude column in the top row. Now find the row with your actual dive depth in the left column. The number where the altitude column intersects the depth row is the adjusted depth. Use this depth in your standard dive table (instead of the actual depth), calculating bottom times, surface intervals, and residual nitrogen as usual.